hdu 1789 贪心算法
http://acm.hdu.edu.cn/showproblem.php?pid=1789
此题大致思路，既然要计算最少扣多少分，就要在最后时间之前把扣分最多的作业先安排了。如果扣分一样多的话，那必然要把时间比较紧的先安排了。所以先按扣分的高低，由高向低排序，如果两门课扣分相同就按他们的结束时间由低向高排序！然后安排即可！
#include<stdio.h>#include<stdlib.h>#include<string.h>#define N 1000int f[N+5];struct T{ int deadline; int score;}homework[N+5];int cmp(const void*a,const void*b){ if((*(struct T*)a).score!=(*(struct T*)b).score) return (*(struct T*)b).score-(*(struct T*)a).score; else return (*(struct T*)a).deadline-(*(struct T*)b).deadline;}int main(){ int C,n,i,j,sum; scanf("%d",&C); while(C--) { memset(f,0,sizeof(f)); scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&homework[i].deadline); for(i=0;i<n;i++) scanf("%d",&homework[i].score); qsort(homework,n,sizeof(homework[0]),cmp); for(i=0,sum=0;i<n;i++) { for(j=homework[i].deadline;j>0;j--) //从最后的期限开始考虑前几天有没有被安排 { if(f[j]==0) { f[j]=1;break; } } if(j==0) //如果一直到结束都没有空余时间，最后只能扣分 sum+=homework[i].score; } printf("%d\n",sum); } return 0;}