现在的位置: 首页 > 综合 > 正文

hdu1798

2018年12月31日 ⁄ 综合 ⁄ 共 665字 ⁄ 字号 评论关闭

贪心

要想减少的分数最小,所以要在最后完成时间之前把扣分最多的要完成,所以按照扣除分数的大小排序,这里有个问题,就是排完序后面的规定时间可能小于前边的,选择前边作业的完成时间要尽量大,为后面的作业留下时间。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int time[1010];
struct op
{
	int t,cont;
}p[1010];
int cmp(const void *a,const void *b)
{
	struct op *c,*d;
	c=(struct op *)a;
	d=(struct op *)b;
	if(c->cont!=d->cont)
		return d->cont-c->cont;
	else return c->t-d->t; 
}
int main()
{
	int i,j,sum,n,t;
	scanf("%d",&t);
	while(t--)
	{
         scanf("%d",&n);
		 for(i=0;i<n;i++)
			 scanf("%d",&p[i].t);
		 for(i=0;i<n;i++)
			 scanf("%d",&p[i].cont);
		 qsort(p,n,sizeof(p[0]),cmp);
		 memset(time,0,sizeof(time));
		 sum=0;
		 for(i=0;i<n;i++)
		 {
			 for(j=p[i].t;j>=1;j--)
			 {
				 if(time[j]==0)
				 {
					 time[j]=1;
					 break;
				 }
			 }
			 if(j==0)
				 sum+=p[i].cont;
		 }
		 printf("%d\n",sum);
	}
	return 0;
}

【上篇】
【下篇】

抱歉!评论已关闭.