shop
📝 NOTE 原题
题目描述
小 A 来到了一个商店，商店内有 件物品，每件物品有一个售价 ，小 A 是一个奸商，因此他能够把每件物品以 的价格卖出。
而由于小 A 背包空间有限，他只能买走恰好一件商品。而小 A 每次购买之后，小 B 将有可能将小 A 的物品摧毁，此时小 A 必须继续购买，并且商店不会返还购买这件物品的钱。小 B 至多可以摧毁 件物品。
小 A 的目标是最大化自己的收益。
小 B 的目标是最小化小 A 获得的收益，即卖出的商品所得减去购买所有物品的总花费。
注意到任何时刻小 B 都可以选择不将小 A 手中的物品摧毁，这样小 A 就必须立刻带着这件物品离开商店。
输入格式
第一行一个正整数 ，表示数据组数。
对于每组数据：
第一行两个正整数 ，分别表示物品数目和小 B 可摧毁的物品数量。
接下来 行，每行两个正整数 ，表示第 件物品的售价和小 A 能卖出的价格。
输出格式
对于每组数据，一行一个整数表示小 A 最终能获得的最大收益。由于小 A 可以直接走出商店（什么都不买），这个收益显然是非负的。
数据范围
， ， ， 。
这个问题看起来就很难以下手，因为它涉及到了两个人都要以最优策略进行，我们思考是否能对它进行转化，以方便我们进行处理。
而以下便是一种合理的转化方案：
设 为一个 的排列，小 A 需要找到最优的 ，使 最大。
这个东西仍然不好处理，我们似乎很难设计一个状态去达到这道题所要求的最优化状态。不过，有的时候如果最优化问题比较复杂，我们可以考虑一下是否能把它转为可行性问题来分析。尝试二分一个答案 ，则我们需要判断 是否可达，实际上，也就是要求在最优 下，有
不过就算如此，这个 还是很讨厌，研究我们是否有去掉 的方法。经过一些思考，我们可以得出关于 的一个结论：
我们可以通过反证法来证明这一结论，若 ，设 ，则我们求出的价值应为
若交换 ，价值变为
显然新价值无论如何都比旧价值大，通过简单的比较就可以得出，故无论如何，均有 。
所以我们先将商品按照从小到大排序，然后考虑顺着选择 ，使 。我们可以设 表示我们当前考虑到第 个物品，选了 个物品，且保证 下，最小的 。
将状态全部初始化为 ，令 ，则转移
时间复杂度 ，仍然无法通过。
如果再多思考一点，会发现它其实满足贪心的性质：假如我已知前 个物品中最多可以选 个满足 ，且使 最小，那么我们若能选第 个，必然满足 才可以。所以若可以选，我们则选。若不可以选，那么当 时，我们不妨交换最大值与 ，因为这样能使 最小，而且可以说明这样做可行性不会被破坏，用堆维护即可。
时间复杂度 。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pr pair<int,int>
#define fi first
#define se second
int n,m;
int const MAX=1e5+10;
pr a[MAX];
bool check(__int128 val){
__int128 res=0;
int cnt=0;
priority_queue<int> Q;
for(int i=1;i<=n;i++){
if(a[i].se-a[i].fi-res>=val){
res+=a[i].fi;
cnt++;
Q.push(a[i].fi);
}else{
if(!Q.empty()&&Q.top()>a[i].fi){
res-=Q.top();
res+=a[i].fi;
Q.pop();
Q.push(a[i].fi);
}
}
}
return cnt>m;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i].fi>>a[i].se;
sort(a+1,a+n+1,[](pr t1,pr t2){return t1.se<t2.se;});
__int128 ans=0,l=0,r=1e18+1;
while(l<=r){
__int128 mid=(l+r)/2;
if(check(mid)){
ans=mid;
l=mid+1;
}else r=mid-1;
}
cout<<(long long)ans<<"\n";
}
signed main(){
freopen("shop.in","r",stdin);
freopen("shop.out","w",stdout);
int T;
cin>>T;
while(T--)solve();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pr pair<int,int>
#define fi first
#define se second
int n,m;
int const MAX=1e5+10;
pr a[MAX];
bool check(__int128 val){
__int128 res=0;
int cnt=0;
priority_queue<int> Q;
for(int i=1;i<=n;i++){
if(a[i].se-a[i].fi-res>=val){
res+=a[i].fi;
cnt++;
Q.push(a[i].fi);
}else{
if(!Q.empty()&&Q.top()>a[i].fi){
res-=Q.top();
res+=a[i].fi;
Q.pop();
Q.push(a[i].fi);
}
}
}
return cnt>m;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i].fi>>a[i].se;
sort(a+1,a+n+1,[](pr t1,pr t2){return t1.se<t2.se;});
__int128 ans=0,l=0,r=1e18+1;
while(l<=r){
__int128 mid=(l+r)/2;
if(check(mid)){
ans=mid;
l=mid+1;
}else r=mid-1;
}
cout<<(long long)ans<<"\n";
}
signed main(){
freopen("shop.in","r",stdin);
freopen("shop.out","w",stdout);
int T;
cin>>T;
while(T--)solve();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pr pair<int,int>
#define fi first
#define se second
int n,m;
int const MAX=1e5+10;
pr a[MAX];
bool check(__int128 val){
__int128 res=0;
int cnt=0;
priority_queue<int> Q;
for(int i=1;i<=n;i++){
if(a[i].se-a[i].fi-res>=val){
res+=a[i].fi;
cnt++;
Q.push(a[i].fi);
}else{
if(!Q.empty()&&Q.top()>a[i].fi){
res-=Q.top();
res+=a[i].fi;
Q.pop();
Q.push(a[i].fi);
}
}
}
return cnt>m;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i].fi>>a[i].se;
sort(a+1,a+n+1,[](pr t1,pr t2){return t1.se<t2.se;});
__int128 ans=0,l=0,r=1e18+1;
while(l<=r){
__int128 mid=(l+r)/2;
if(check(mid)){
ans=mid;
l=mid+1;
}else r=mid-1;
}
cout<<(long long)ans<<"\n";
}
signed main(){
freopen("shop.in","r",stdin);
freopen("shop.out","w",stdout);
int T;
cin>>T;
while(T--)solve();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pr pair<int,int>
#define fi first
#define se second
int n,m;
int const MAX=1e5+10;
pr a[MAX];
bool check(__int128 val){
__int128 res=0;
int cnt=0;
priority_queue<int> Q;
for(int i=1;i<=n;i++){
if(a[i].se-a[i].fi-res>=val){
res+=a[i].fi;
cnt++;
Q.push(a[i].fi);
}else{
if(!Q.empty()&&Q.top()>a[i].fi){
res-=Q.top();
res+=a[i].fi;
Q.pop();
Q.push(a[i].fi);
}
}
}
return cnt>m;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i].fi>>a[i].se;
sort(a+1,a+n+1,[](pr t1,pr t2){return t1.se<t2.se;});
__int128 ans=0,l=0,r=1e18+1;
while(l<=r){
__int128 mid=(l+r)/2;
if(check(mid)){
ans=mid;
l=mid+1;
}else r=mid-1;
}
cout<<(long long)ans<<"\n";
}
signed main(){
freopen("shop.in","r",stdin);
freopen("shop.out","w",stdout);
int T;
cin>>T;
while(T--)solve();
return 0;
}