`
java-mans
  • 浏览: 11314072 次
文章分类
社区版块
存档分类
最新评论

hdu17891 Doing Homework again 贪心

 
阅读更多

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1789

//题目的意思是安排做作业的顺序,使得被扣的分数最少
//贪心策略:先按时间顺序递增排序,若时间相同按分数递减排序。
//然后从下标为0~n-1逐个检查,若时间够的话加入优先队列,
//若不够从队列中找出最小的分数与当前比较,若当前的分数高则替换。

#include<iostream>
#include<cstdlib>
#include<queue>
using namespace std;
struct Work
{
	int time,score;
};
class cmp
{
public:
	bool operator()(int x,int y)
	{return x>y;}
};
priority_queue<int,vector<int>,cmp> Q;
int cmp(const void *a,const void *b)
{
	if((*(Work*)a).time==(*(Work*)b).time)
		return (*(Work*)b).score-(*(Work*)a).score;
	return (*(Work*)a).time-(*(Work*)b).time;
}
int main()
{
	int cas;
	cin>>cas;
	while(cas--)
	{
		int n,i;
		cin>>n;
		struct Work *s=new Work[n];
		for(i=0;i<n;i++)
			cin>>s[i].time;
		int sum=0,cnt=0;
		for(i=0;i<n;i++)
		{
			cin>>s[i].score;
			sum+=s[i].score;
		}
		qsort(s,n,sizeof(s[0]),cmp);
		
		
		for(i=cnt;i<n;i++)
		{
			if(cnt<s[i].time)
			{
				Q.push(s[i].score);
				cnt++;
			}
			else
			{
				int temp=Q.top();
				if(temp<s[i].score)
				{
					Q.pop();
					Q.push(s[i].score);
				}
			}
		}
		for(i=0;i<cnt;i++)
			sum-=Q.top(),Q.pop();
		printf("%d\n",sum);
		
	}
	return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics