题解：CF1969D Shop Game
GY程袁浩
·
·
题解
思路
考虑 Bob 的策略：
如果 Alice 选了物品 i，那么 Bob 如果选了物品 i 会使得 Alice 对于这个物品亏多少钱。
原来赚的钱：b_{i}-a_{i}。
Bob 选后本金的亏损：-a_{i}。
那么 Bob 如果选了物品 i 会就使得 Alice 对于这个物品亏：
所以我们知道 Bob 应该选前 $k$ 大 $b_{i}$ 的 $i$ 才能使在目前 Alice 选出的物品中让他亏损最多。
### 考虑 Alice 的策略：
首先 Alice 选出的前 $k$ 大的物品一定不赚钱。
那么如果选的物品不多于 $k$ 且至少选了一个物品，就一定是亏的，在最坏的情况下，我们可以什么都不选来保证不亏钱。
所以可以选 $k$ 个物品来献祭，来让其它选的物品赚钱，但也不是选哪个献祭都可以，那 $k$ 个献祭的物品的 $b_{i}$ 必须在所有选出的物品的 $b$ 里是前 $k$ 大。
那么如何才能让献祭的物品由我们选择呢？可以选择将 $b$ 由大到小排序，这样最左边的我们选择的 $k$ 个物品就一定是献祭的，又由于我们需要献祭的钱最少，所以选 $a_{i}$ 前 $k$ 小的 $i$ 就可以了。那么选的第 $k$ 个物品往后怎么选？只需要挑 $b_{i}>a_{i}$ 的选就行了，因为如果选其它的必然不赚钱。
但是我们不能只考虑前 $k$ 个物品献祭，所以要枚举考虑献祭的最后一个 $i$ 的分界线。
## 做法
将 $b_{i}$ 排序，预处理 $i$ 到 $n$ 的买入价小于卖入价物品的利润，建立大根堆，存考虑到献祭的前 $k$ 小的 $a_{i}$，维护堆内和。接下来枚举考虑献祭的最后一个 $i$，将 $a_{i}$ 入堆，如果堆的大小大于 $k$ 那么弹出堆顶。左边选前 $k$ 小 $a_{i}$ 的 $i$ 物品，右边选 $b_{i}>a_{i}$ 的 $i$ 物品。用右边利润和减去堆内和来更新 $ans$ 的最大值。
注意 $k$ 为 $0$ 时要特判，因为后面的做法考虑的是 Bob 至少选一个物品。
$ans$ 一开始初值为 $0$，因为 Alice 可以什么都不选。
那么这道题就做完了，代码其实不长。
## Code
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
bool cmp(pair<int,int> x,pair<int,int> y)
{
return x.first>y.first;
}
signed main()
{
int tt;
cin>>tt;
while(tt--)
{
int n,k;
cin>>n>>k;
vector<pair<int,int> > a(n+1);
vector<int> pre(n+2);
for(int i=1;i<=n;i++) cin>>a[i].second;
for(int i=1;i<=n;i++) cin>>a[i].first;
sort(a.begin()+1,a.end(),cmp);
for(int i=n;i>=1;i--) pre[i]=max(a[i].first-a[i].second,(int)0)+pre[i+1];
priority_queue<int> q;
int ans=0,sum=0;
if(k==0)
{
cout<<pre[1]<<endl;
continue;
}
for(int i=1;i<=n;i++)
{
q.push(a[i].second);
sum+=a[i].second;
if(q.size()>k&&q.size()) sum-=q.top(),q.pop();
if(q.size()==k) ans=max(ans,pre[i+1]-sum);
}
cout<<ans<<endl;
}
}
```