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;
}