class Solution {
public:
long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
}
};
2542. 最大子序列的分数
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都是 n ，再给你一个正整数 k 。你必须从 nums1 中选一个长度为 k 的 子序列 对应的下标。
对于选择的下标 i0 ，i1 ，...， ik - 1 ，你的 分数 定义如下：
nums1 中下标对应元素求和，乘以 nums2 中下标对应元素的 最小值 。(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]) 。请你返回 最大 可能的分数。
一个数组的 子序列 下标是集合 {0, 1, ..., n-1} 中删除若干元素得到的剩余集合，也可以不删除任何元素。
示例 1：
输入：nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3 输出：12 解释： 四个可能的子序列分数为： - 选择下标 0 ，1 和 2 ，得到分数 (1+3+3) * min(2,1,3) = 7 。 - 选择下标 0 ，1 和 3 ，得到分数 (1+3+2) * min(2,1,4) = 6 。 - 选择下标 0 ，2 和 3 ，得到分数 (1+3+2) * min(2,3,4) = 12 。 - 选择下标 1 ，2 和 3 ，得到分数 (3+3+2) * min(1,3,4) = 8 。 所以最大分数为 12 。
示例 2：
输入：nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1 输出：30 解释： 选择下标 2 最优：nums1[2] * nums2[2] = 3 * 10 = 30 是最大可能分数。
提示：
n == nums1.length == nums2.length1 <= n <= 1050 <= nums1[i], nums2[j] <= 1051 <= k <= n原站题解
golang 解法, 执行用时: 148 ms, 内存消耗: 11.5 MB, 提交时间: 2023-01-23 10:33:03
func maxScore(nums1, nums2 []int, k int) int64 {
type pair struct{ x, y int }
a := make([]pair, len(nums1))
sum := 0
for i, x := range nums1 {
a[i] = pair{x, nums2[i]}
}
sort.Slice(a, func(i, j int) bool { return a[i].y > a[j].y })
h := hp{nums2[:k]} // 复用内存
for i, p := range a[:k] {
sum += p.x
h.IntSlice[i] = p.x
}
ans := sum * a[k-1].y
heap.Init(&h)
for _, p := range a[k:] {
if p.x > h.IntSlice[0] {
sum += p.x - h.replace(p.x)
ans = max(ans, sum*p.y)
}
}
return int64(ans)
}
type hp struct{ sort.IntSlice }
func (hp) Pop() (_ interface{}) { return }
func (hp) Push(interface{}) {}
func (h hp) replace(v int) int { top := h.IntSlice[0]; h.IntSlice[0] = v; heap.Fix(&h, 0); return top }
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 192 ms, 内存消耗: 36.4 MB, 提交时间: 2023-01-23 10:32:47
'''
请记住：有序是一个非常好的性质。
把nums1和nums2 组合起来，按照nums2[i] 从大到小排序。枚举nums2[i] 作为序列的最小值，
那么nums1就只能在下标 ≤i 的数中选了。要选最大的k 个数。
'''
class Solution:
def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
a = sorted(zip(nums1, nums2), key=lambda p: -p[1])
h = [x for x, _ in a[:k]]
heapify(h)
s = sum(h)
ans = s * a[k - 1][1]
for x, y in a[k:]:
if x > h[0]:
s += x - heapreplace(h, x)
ans = max(ans, s * y)
return ans