题目描述

难度分:$1063$

输入$T(\leq 2 \times 10^5)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n$、$k(1 \leq k \leq n \leq 2 \times 10^5)$，长为$n$的数组$a(1 \leq a[i] \leq 10^6)$，长为$n$的数组$b(1 \leq b[i] \leq 10^6)$。

你需要从$n$个下标中选择恰好$k$个下标，组成集合$S$。

输出$max_{i \in S}a[i] \times \Sigma_{i \in S}b[i]$的最小值。

输入样例

3
3 2
3 7 6
9 2 4
5 3
6 4 1 5 9
8 6 5 1 7
10 6
61 95 61 57 69 49 46 47 14 43
39 79 48 92 90 76 30 16 30 94

输出样例

42
60
14579

算法

反悔贪心

比较明显的一个反悔贪心，先将$a$和$b$打包成一个二元组数组$tup$，其中$tup[i]=(a[i],b[i])$。然后将$tup$按照第一个关键字排序，这样$a$就是有序的了，初始化答案为前$k$个元素的目标函数值。

然后考虑将$mx=max_{i \in S}a[i]$变大，$sum=\Sigma_{i \in S}b[i]$减小，遍历$i \in [k,n)$，如果将$i$加入到集合中，那么因为$tup$按照$a$排好序了，肯定有$mx=a[i]$成立。而要想把$sum$尽量减小，在$b[i]$已经加入到$sum$的情况下，只需要让另外$k-1$个$b[idx]$是$[1,i-1]$中$b$最小的$k-1$个。

这样一来，用一个大根堆维护$[1,i]$中最小的$k$个$b[i]$，并维护这些$b[i]$的累加和$sum$，然后不断维护$mx \times sum$的最小值即可。

复杂度分析

时间复杂度

对$tup$排序的时间复杂度为$O(nlog_2n)$。遍历$i \in [1,n]$进行反悔贪心，每个$i$可能需要进行小根堆的弹出和压入操作，时间复杂度也为$O(nlog_2n)$。所以整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

$tup$数组的空间复杂度为$O(n)$，大根堆在最差情况下需要压入$O(k)$个$b$数组中的值。所以整个算法的额外空间复杂度为$O(n+k)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int t, n, k;

LL solve(vector<array<int, 2>>& tup) {
    sort(tup.begin(), tup.end());
    LL ans = 0, sum = 0;
    priority_queue<int> heap;
    for(int i = 0; i < k; i++) {
        sum += tup[i][1];
        heap.push(tup[i][1]);
    }
    ans = sum * tup[k - 1][0];
    for(int i = k; i < n; i++) {
        int mx = tup[i][0];
        if(heap.top() > tup[i][1]) {
            sum += tup[i][1] - heap.top();
            heap.pop();
            heap.push(tup[i][1]);
            ans = min(ans, mx * sum);
        }
    }
    return ans;
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &k);
        vector<int> a, b;
        for(int i = 0; i < n; i++) {
            int num;
            scanf("%d", &num);
            a.push_back(num);
        }
        for(int i = 0; i < n; i++) {
            int num;
            scanf("%d", &num);
            b.push_back(num);
        }
        vector<array<int, 2>> tup;
        for(int i = 0; i < n; i++) {
            tup.push_back({a[i], b[i]});
        }
        printf("%lld\n", solve(tup));
    }
    return 0;
}