HDU 1789 Doing Homework again【贪心】

题意:给出n个作业的截止时间,和该作业没有完成会被扣掉的分数。问最少会被扣掉多少分。

第一次做这一题是好久之前,当时不会(不会处理两个关键字关系@_@)---现在还是不会---看了题解---原来是这样的---

因为要使得扣的分数尽可能少,那就先把扣分多的作业做了,即按照扣分降序排序,再遍历看该份作业能不能完成,不能完成则扣去相应的分数

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm> 
#define maxn 10005 
using namespace std;
int used[maxn];
struct node
{
	int d,p;
} a[maxn];
int cmp(node n1,node n2)
{
	return n1.p>n2.p;
}
int main()
{
	int ncase,n,i,j,ans;
	scanf("%d",&ncase);
	while(ncase--)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++) scanf("%d",&a[i].d);
		for(i=1;i<=n;i++) scanf("%d",&a[i].p);
		sort(a+1,a+1+n,cmp);
		memset(used,0,sizeof(used));
		ans=0;
		
		for(i=1;i<=n;i++)
		{
			for(j=a[i].d;j>=1;j--)
			{
				if(!used[j])
				{
					used[j]=1;
					break;
				}				
			}
			if(j==0) ans+=a[i].p;
		}
		printf("%d
",ans);		
	}
}

  

原文地址:https://www.cnblogs.com/wuyuewoniu/p/4289685.html