Cooking Time Gym - 101498F 贪心

题目链接:
Cooking Time
题目大意:
有一个冰箱,有N个调味品,一开始所有调味品都在冰箱内.外面最多放置 K个调味品
你要按给定的顺序来拿取调味品,如果外面有调味品那么直接取用即可,如果没有需要打开冰箱,如果外面放置数达到K了,那么需要放回一个.
现在要求最少要开几次冰箱

分析:
贪心地去放回调味品,将后面没有再继续用的调味品放回.
如果都一样那么任意返回一个即可.原因是无论重复次数和先后顺序多少,都要记一次取用.
那么用 pii 单调单调队列就可以了.

预处理每个调味品编号和下一个相同调味品的位置 nxt[i]

实际上是一个线性过程

代码实现;

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define inf 0x3f3f3f3f
#define mem(s,t) memset(s,t,sizeof s)
typedef pair<int,int> pii;
const int MAXN =1e5+10;
int n,k;
priority_queue<pii,vector<pii> > pq;
map<int,int> m;
int a[MAXN],lst[MAXN],nxt[MAXN],inque[MAXN];
int main() {
int T;
scanf("%d",&T);
while(T--){
m.clear();
while(!pq.empty()) pq.pop();
mem(nxt,0);
mem(inque,0);
scanf("%d%d",&n,&k);
int cnt=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(!m.count(a[i])) m[a[i]]=++cnt;//重新编号
lst[i]=n;
inque[i]=0;
nxt[i]=0;
}
for(int i=0;i<n;i++) a[i]=m[a[i]];
for(int i=n-1;i>=0;i--){//预处理下一个位置
nxt[i]=lst[a[i]];
lst[a[i]]=i;
}
int ans=0;
for(int i=0;i<n;i++){
//cout<<inque[a[i]]<<endl;
if(inque[a[i]]){
pq.push(make_pair(nxt[i],a[i]));//将下一个入队
continue;
}
if(k){
k--;
ans++;
inque[a[i]]=1;
pq.push(make_pair(nxt[i],a[i]));
}
else {
ans++;
while(!inque[pq.top().second]) pq.pop();//将已经不在队里的清空
inque[pq.top().second]=0;
pq.pop();
inque[a[i]]=1;
pq.push(make_pair(nxt[i],a[i]));
}
}
cout<<ans<<endl;
}
return 0;
}

最后

以上就是无私咖啡最近收集整理的关于Cooking Time Gym - 101498F 贪心的全部内容，更多相关Cooking内容请搜索靠谱客的其他文章。