此題大致思路，既然要計算最少扣多少分，就要在最後時間之前把扣分最多的作業先安排了。如果扣分一樣多的話，那必然要把時間比較緊的先安排了。所以先按扣分的高低，由高向低排序，如果兩門課扣分相同就按他們的結束時間由低向高排序！然後安排即可！ [cpp] #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 1000 int 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; }
