CF1969D Shop Game 题解

题目链接：Shop Game

题意：

Alice 和 Bob 正在商店里玩游戏。商店里有 $n$ 件商品

每件商品有两个参数： $a_i$（Alice 买进的物品价格）和 $b_i$（愿意出的物品价格）。

Alice 希望选择一个商品子集（可能是空）并购买它们。之后，Bob 会执行以下操作：

如果 Alice 购买的物品少于 $k$，Bob 可以免费拿走所有物品；

否则，他会免费拿走 Alice 购买的 $k$ 个物品（由 Bob 选择是哪些 $k$ 个物品），至于其他被选中的物品，Bob 会从 Alice 那里购买，并为 $i$ 号物品支付 $b_i$。

Alice 的利润等于 $\sum\limits_{i\in S}b_i-\sum\limits_{j \in T}a_j$，其中 $S$ 是 Bob 从 Alice 处购买的物品集，$T$ 是 Alice 从商店购买的物品集。换句话说，Alice 的利润就是 Bob 支付给她的金额和她购买商品所花费的金额之间的差额。

Alice 希望自己的利润最大化，而 Bob 希望 Alice 的利润最小化。您的任务是计算在 Alice 和 Bob 都采取最优行动的情况下 Alice 的利润。

输入格式：

第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ )——测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ （ $1 \le n \le 2 \cdot 10^5$，$0 \le k \le n$ ）。

第二行包含 $n$ 整数 $a_1, a_2, \dots, a_n$ （ $1 \le a_i \le 10^9$ ）。

第三行包含 $n$ 整数 $b_1, b_2, \dots, b_n$ （ $1 \le b_i \le 10^9$ ）。

输出格式：

对于每个测试用例，打印一个整数——如果Alice和Bob都采取最优行为，则Alice的利润。

可以发现就是要选若干个物品，除了 $b_i$ 最大的 $k$ 个价值强制为 $-a_i$ ，否则价值 $b_i - a_i$ 。

我们对物品按 $b_i$ 从大到小排序，并预处理后缀和 $S_i=b_i-a_i$ ，显然 $k=0$ 时答案就是 $S_1$ 。

否则我们在 $[1,i]$ 中选 $k$ 个 $a_i$ 最小的物品，这个可以用优先队列维护全局 $k$ 小值的办法算出来

然后用这 $k$ 个物品的 $-a_i$ 加上 $S_{i+1}$ 去更新答案。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))
#define Fi first
#define Se second

int suf[N];
pii a[N]; priority_queue<int> q;
void solve()
{
    int n, k; cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i].Fi;
    for(int i = 1; i <= n; i++) cin >> a[i].Se;
    sort(a + 1, a + 1 + n, [](pii a, pii b) { return a.Se > b.Se; });
    int res = 0, sum = 0; suf[n + 1] = 0; while(!q.empty()) q.pop();
    for(int i = n; i >= 1; i--) suf[i] = max(a[i].Se - a[i].Fi, 0ll) + suf[i + 1];
    if(!k) return cout << suf[1] << '\n', void(0);
    for(int i = 1; i <= n; i++)
    {
        q.push(a[i].Fi); sum += a[i].Fi;
        if(q.size() > k) { sum -= q.top(); q.pop(); }
        if(q.size() == k) up(res, suf[i + 1] - sum);
    }
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}