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