#C241111B. 游乐园
标签（Label）
- 反悔贪心
网址（Website）
题目（Problem）
题解（Solution）
先选出玩这 $k$ 个项目用时最少的方案：选 $k$ 个项目，全部用票。
最重要的就是这个：先求出选 $k$ 个项目最小的时间花费。
后面的只要每个操作都是贪心的，那么就可以推出来了。
出题者题解
算法分析
这题有很多做法，这里说一个反悔贪心。
首先答案小于等于 $k$ 是容易判断的，只要把 $b_i$ 最小的 $k$ 个能选几个选几个即可。否则我们先选 $b_i$ 最小的 $k$ 个——这是玩 $k$ 个项目中用时最少的一种方案，然后我们尝试增加一个项目，有两种可能。
- 新加一个 $a_i$。
- 新加一个 $b_i$，把之前的某个 $b_j$ 换成 $a_j$。
为了计算两种代价，我们需要维护三个堆：
- 目前不玩项目的 $a_i$ 的代价；
- 目前不玩的项目的 $b_i$ 的代价；
- 目前玩的项目里是 $b_i$ 换 $a_i$ 的代价。
维护好三个堆就很方便算贡献了。
时间复杂度：$O(n \log n)$。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i++)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 501234;
bool ST;
double Tim;
int a[N],b[N],c[N];
int n,k,lmt,t,ans;
P g[N];
set<P> s1,s2,s3;
void Solve(){
n=rd(),k=rd(),lmt=rd();For(i,1,n) g[i]={rd(),rd()};
sort(g+1,g+n+1,[&](auto a,auto b){return a.y<b.y;});
For(i,1,n) tie(a[i],b[i])=g[i];
For(i,k+1,n) s1.emplace(a[i],i);
For(i,k+1,n) s2.emplace(b[i],i);
For(i,1,k){
s3.emplace(a[i]-b[i],i);
if(t+b[i]<=lmt) t+=b[i],ans++;
else return printf("%lld\n",ans),void();
}
For(i,k+1,n){
if(s1.begin()->x < s2.begin()->x + s3.begin()->x){//直接加入a[i]
if(t+s1.begin()->x<=lmt){
t += s1.begin()->x,
ans++;
int j=s1.begin()->y;
s1.erase({a[j],j}),
s2.erase({b[j],j});
}
}else{
if(t+s2.begin()->x+s3.begin()->x<=lmt){
t += s2.begin()->x+s3.begin()->x,
ans++;
int j=s2.begin()->y, k=s3.begin()->y;
s1.erase({a[j],j}),
s2.erase({b[j],j});
s3.emplace(a[j]-b[j],j);
s3.erase({a[k]-b[k],k});
}
}
}printf("%lld\n",ans);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("park.in","r",stdin);
freopen("park.out","w",stdout);
int Tt=1;Tim=clock();
while(Tt--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
