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 ;
}