贪心,,每次选限制时间最小的工作完成,完成时的时间递增,而限制的时间也是递增的,所以差值最小
#include<stdio.h> #include<string.h> #include<stdlib.h> struct op { int s,e; }p[100001]; int cmp(const void *a,const void *b) { op *c,*d; c=(op *)a; d=(op *)b; if(c->e!=d->e) return c->e-d->e; return c->s-d->s; } int main() { int i,n,op=1,t; __int64 sum,max; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i<n;i++) scanf("%d%d",&p[i].s,&p[i].e); qsort(p,n,sizeof(p[0]),cmp); sum=0;max=0; for(i=0;i<n;i++) { sum+=p[i].s; if(max<sum-p[i].e) max=sum-p[i].e; } printf("Case %d: ",op++); printf("%I64d\n",max); } return 0; }