Codevs No.1052 地鼠游戏

2016-05-31 18:22:32

题目链接: 地鼠游戏 Codevs No.1245

题目大意:

  打地鼠,一开始所有地鼠都出现,但是维持的时间(s)和击中所得的积分各不同,求出采用最优策略(1s打一个)打地鼠所得

解法:

  贪心+堆优化

  按时间倒着选,每次将当前时间结束的地鼠加入集合

  每秒在最大堆中取最上端的点加入答案即可

需要注意的地方:

  1.时间顺序一定要对,正着选是错的

 //地鼠游戏 (Codevs No.1052)
//贪心
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=;
struct node
{
int key;
int time;
};
node F[maxn];
bool comp(node a,node b)
{
return a.time>b.time;
}
priority_queue <int> q;
int ans;
int N;
int main()
{
scanf("%d",&N);
for(int i=;i<=N;i++)scanf("%d",&F[i].time);
for(int i=;i<=N;i++)scanf("%d",&F[i].key);
sort(F+,F+N+,comp);
int now=F[].time;
int loc=;
while(now)
{
while(F[loc].time==now)
{
q.push(F[loc].key);
loc++;
}
if(!q.empty())
{
ans+=q.top();
q.pop();
}
now--;
}
printf("%d",ans);
return ;
}
上一篇:二.Nginx反向代理和静态资源服务配置


下一篇:IOS网络第二天 - 04-黑酷-GDataXML 解析