本文主要是介绍Codevs P1052 地鼠游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
地鼠游戏
大贪心
此题可以用DP解
但是贪心也是对的
思路
在地鼠缩回地里之前都是可以敲掉的
可以考虑优先队列
时间倒着流逝凡是在时间范围内的地鼠都压进堆里
每秒敲的时候就可以取堆头元素 保证敲得是价值最高的
代码
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;priority_queue <int> q;const int Maxn=101;int n,ans;struct node {int t,x;}mouse[Maxn];bool comp(node a,node b){return a.t<b.t;}int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&mouse[i].t);for(int i=1;i<=n;i++)scanf("%d",&mouse[i].x);sort(mouse+1,mouse+n+1,comp);int cur=n,maxt=mouse[n].t;while(maxt>0){while(mouse[cur].t>=maxt){q.push(mouse[cur].x);cur--;}if(!q.empty()){ans+=q.top();q.pop();}maxt--;}printf("%d",ans);return 0;
} End。
这篇关于Codevs P1052 地鼠游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
