SP688 SAM - Toy Cars题解

398 字
2 分钟
SP688 SAM - Toy Cars题解

双倍经验P3419#

其实我第一眼看到这道题的时候以为是一道 DP\texttt{DP},但是想了想就发现要记录的状态实在太多,于是就去想贪心。

考虑每次拿玩具对总体的贡献,因为能同时放在地上的玩具个数有限,而我们又只计算拿玩具下来的次数,于是便可得出一个贪心结论,那便是对于把玩具放回去这个行为,下一次玩这个玩具的时间距离现在越远一定越优,因为我们不能不玩任何一个玩具。

所以我们在把玩的顺序读入后,倒序枚举预处理出这个玩具下一次玩的时间,那么至于如何选择,只需要用一个优先队列维护即可,因为要存两维,一个是用来排序的 next\texttt{next} 数组,一个是这个玩具的 id\texttt{id},所以我们用优先队列存一个 pair\texttt{pair} 类即可。

复杂度为跑不满的 O(nlogn)\mathrm{O}(nlogn)。

另外温馨提示,多测不清空,爆零两行泪。

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,k,p,a[N],nex[N],temp[N],ans,vis[N],tot;
priority_queue<int,vector<pair<int,int>>>q;
//也可以这样写
// priority_queue<pair<int,int>>q;
void init(){//预处理函数
while(!q.empty()){
q.pop();
}
memset(temp,0,sizeof temp);
memset(nex,0,sizeof nex);
memset(vis,0,sizeof vis);
ans=0;
}
int main(){
int T;
scanf("%d",&T);
for(int l=1;l<=T;l++){
scanf("%d%d%d",&n,&k,&p);
for(int i=1;i<=p;i++){
scanf("%d",&a[i]);
}
for(int i=p;i>=1;i--){//预处理出nex数组
if(temp[a[i]]==0) nex[i]=1e6;
else nex[i]=temp[a[i]];
temp[a[i]]=i;
}
for(int i=1;i<=p;i++){
if(!vis[a[i]]){
if(q.size()==k){
vis[q.top().second]=0;
q.pop();
}
q.push(make_pair(nex[i],a[i]));
ans++;
vis[a[i]]=1;
}else{//因为有新的进入队列更新,而优先队列不好维护弹出,所以把范围开大一个,防止错误弹出
k++;
q.push(make_pair(nex[i],a[i]));
}
}
printf("%d\n",ans);
init();
}
return 0;
}

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

SP688 SAM - Toy Cars题解
https://rechenz.github.io/post/sp688/
作者
热尘
发布于
2023-06-12
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
热尘
游戏开发者 · AI 爱好者
公告
欢迎来到我的博客!这是一则示例公告。
分类
标签
站点统计
文章
38
分类
5
标签
12
总字数
46,029
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录