题目描述

难度分:$1900$

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

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

有$n$个商品，Alice买进价格是$a[i]$，卖给Bob的价格是$b[i]$。

首先Alice从$a$中选一个子集$sub$，并花费$sum(sub)$元钱$sub$可以为空。

如果$sub$的大小$\leq k$，那么这些商品免费给Bob。

否则Bob选择其中的$k$个商品免费拿走，剩余的商品花费$b[i]$购买。

Alice的利润为从Bob那赚到的钱，减去购买商品的钱。Alice希望自己的利润最大化，而Bob希望Alice的利润最小化。输出在Alice和Bob都采取最优行动的情况下，Alice的利润。

输入样例

4
2 0
2 1
1 2
4 1
1 2 1 4
3 3 2 3
4 2
2 1 1 1
4 2 3 2
6 2
1 3 4 9 1 3
7 6 8 10 6 8

输出样例

1
1
0
7

算法

贪心

看着像是博弈论，但其实二人的最优策略可以贪出来。不管Alice选哪个子集，Bob一定会选择这个子集里面自己花费最高的免费拿走，这时候Alice会损失$\Sigma_{i}a[i]$，而Alice要想赚钱最多，子集剩下的那一部分肯定是希望$b[i]-a[i]$尽可能大。

因此我们将所有商品按照$b$值降序排列，Bob免费拿走的一定是前缀属于Alice选出的子集中$a[i]$最小的$k$个（前缀中$b$值比后面大，不需要考虑$b$值了），这样就能保证Alice的利益最大。

枚举分割点$i$，$\lt i$的位置用大根堆维护最小的$k$个$a[i]$，这些$a[i]$之和就是Alice的代价$cost$，后缀$[i,n]$全部都要，Alice的获利为$income=\Sigma_{j=i}^{n}max(0,b[i]-a[i])$，可以预处理一个后缀和数组$sufsum$。维护所有分割点$i$对应的$income-cost$的最大值就能得到答案。

复杂度分析

时间复杂度

预处理出$sufsum$的时间复杂度为$O(n)$。枚举分割点的时间复杂度为$O(n)$，但可能会存在堆的插入操作，堆中的元素数量在$O(k)$量级，因此得到最终答案的时间复杂度为$O(nlog_2k)$。

空间复杂度

后缀和数组$sufsum$的空间复杂度为$O(n)$。大根堆中最多$O(k)$级别的元素，空间复杂度为$O(k)$。因此，整个算法的额外空间复杂度为$O(n+k)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int T, n, k;
LL sufsum[N];

struct Node {
    int a, b;
    bool operator<(const Node other) const {
        return b > other.b;
    }
} items[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &items[i].a);
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &items[i].b);
        }
        sort(items + 1, items + n + 1);
        sufsum[n + 1] = 0;
        for(int i = n; i >= 1; i--) {
            sufsum[i] = sufsum[i + 1] + max(items[i].b - items[i].a, 0);
        }
        priority_queue<int> heap;
        LL cost = 0;
        for(int i = 1; i <= k; i++) {
            cost += items[i].a;
            heap.push(items[i].a);
        }
        LL ans = 0;
        for(int i = k + 1; i <= n; i++) {
            ans = max(ans, sufsum[i] - cost);
            if(heap.size() && heap.top() > items[i].a) {
                cost += items[i].a - heap.top();
                heap.pop();
                heap.push(items[i].a);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}