贪心+线段树
另一篇用线段树的题解码风自认为有点奇怪,就写一篇(自认为)码风正常一点的
提供一道弱化版P2088 果汁店的难题题目基本一样,范围小了很多
思路比较简单,就是每次需要将玩具放回架子上时,优先放离下次使用最远的玩具
那么我们先预处理出一个next数组(代码中为nxt),来保存对于每个玩具,下一次使用同样的玩具是什么时候
那么线段树用来维护什么呢?我们用线段树来维护每种玩具下一次使用是什么时候。当然,如果这种玩具不在地上,就不加入线段树的维护(因为我们需要用线段树来维护最大值,所以将这种玩具下一次使用的时间设为0)
这样的话,我们每次要将一个新的玩具放到地上时,就要用线段树来查询离下次使用时间最远的一个玩具,然后放回架子上了!
最后就是代码了,细节还是有一点的,需要注意一下
#include<iostream>
using namespace std;
int nxt[500005],book[500005],a[500005];//book数组辅助处理nxt数组,a为初始数组
bool bj[500005];//bj数组记录玩具是否在地上
int maxx[400005],wz[400005];//线段树数组
void up(int root){
if((maxx[root<<1])>(maxx[root<<1|1])){
maxx[root]=maxx[root<<1];
wz[root]=wz[root<<1];
}
else{
maxx[root]=maxx[root<<1|1];
wz[root]=wz[root<<1|1];
}
}
void change(int root,int l,int r,int k,int temp){
if(l==r){maxx[root]=temp;wz[root]=l;return;}
int mid=(l+r)>>1;
if(k<=mid)change(root<<1,l,mid,k,temp);
else change(root<<1|1,mid+1,r,k,temp);
up(root);
}
//----以上是线段树板子
int main(){
int k,q,n,st=0,sum=0;//sum是答案,st记录地上的玩具数目
cin>>k>>q>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
nxt[book[a[i]]]=i;
book[a[i]]=i;
}//处理nxt数组,用book数组记录当种玩具最靠后的位置
for(int i=1;i<=n;i++)if(nxt[i]==0)nxt[i]=999999999;//如果是同种玩具最后一个,nxt设为inf
for(int i=1;i<=n;i++){
if(bj[a[i]]){
change(1,1,k,a[i],nxt[i]);
continue;
}//玩具在地上就直接在线段树上改,然后直接过
if(st<q){
st++;
change(1,1,k,a[i],nxt[i]);
bj[a[i]]=1;
sum++;
continue;
}//玩具还没放满时直接放,线段树上改
int x=wz[1];//找到最远的玩具
change(1,1,k,x,0);//放回架子
change(1,1,k,a[i],nxt[i]);//当前的拿回地上
bj[x]=0;
bj[a[i]]=1;
sum++;//统计答案
}
cout<<sum;
return 0;
}