题解：CF1969D Shop Game

· · 题解

对于 Bob

B 的每次零元购相当于吞掉了 A 本应获得的 b_i 元，这些钱就相当于是 A 净亏的。

考虑当 A 选出商品后花的钱 \sum_{i \in T} a_i 已经定了，这时 B 能做的只有让 A 得的钱尽量少，亏得尽量多，它就会按 b_i 从大到小零元购，这样可以让剩下的 b_i 之和最小，A 得的最少，利润也就最少。

对于 Alice

买少于或等于 k 件物品反正都会被 B 零元薅走，一定亏。所以要么一件都不买，不亏不赚；要么买多于 k 件，才有机会赚。

选出的物品中，b_i 值在前 k 大的是一定会被 B 先零元购的，只有其他商品才能带来利润。所以，将所有商品按 b_i 的值从大到小排序，这样可以保证 B 所选的一定是靠左边的 k 个，而右边剩下的就是可以赚钱的。

枚举拿出去投喂 B 的商品和正常赚钱的商品的分界线。

在分界线左侧，当然是希望净亏的越少越好，所以选择的一定是 a_i 最小的 k 个，这部分可以用优先队列维护选出来的 k 个商品的最大 a_i 值，每次分界线右移的时候如果当前的 a_i 比堆顶最大的还大，那么就一定可以顶掉这个堆顶。弹出堆顶并把这个 a_i 压进去即可。

在分界线右侧，凡是 b_i-a_i>0 的都可以选，所以可以另计一个 sum_i 表示从 i 到 n 只取 b_i-a_i>0 的总利润。

得到每次左侧的最小花费和右侧的最大利润之后，两者结合即可计算出此时实际利润。对所有的分界线算出来再取最大值就是 A 在 B 采取最优策略下所能得到的最大利润。

这个最大利润可能仍然是负数。这个时候不如不取，还需处理一下。

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2e5+5;
int n,k;
pair<int,int> money[N];
long long sum_rev[N];
priority_queue<int> sorry;

bool cmp(pair<int,int> x,pair<int,int> y)
{
    return x.second>y.second;
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) scanf("%d",&money[i].first);
        for(int i=1;i<=n;i++) scanf("%d",&money[i].second);
        sort(money+1,money+n+1,cmp);
        for(int i=n;i>=1;i--)
            sum_rev[i]=sum_rev[i+1]+max(money[i].second-money[i].first,0);
        long long oh_no=0;
        for(int i=1;i<=k;i++)
        {
            sorry.push(money[i].first);
            oh_no+=money[i].first;
        }
        long long ans=0;
        for(int i=k+1;i<=n;i++)
        {
            ans=max(ans,sum_rev[i]-oh_no);
            if(sorry.empty()) continue;
            if(money[i].first<sorry.top())
            {
                oh_no-=sorry.top(); sorry.pop();
                oh_no+=money[i].first; sorry.push(money[i].first);
            }
        }
        printf("%lld\n",ans);

        for(int i=1;i<=n;i++) sum_rev[i]=0;
        while(!sorry.empty()) sorry.pop();
    }
    return 0;
}