hdu 1789 贪心算法

 

此题大致思路，既然要计算最少扣多少分，就要在最后时间之前把扣分最多的作业先安排了。如果扣分一样多的话，那必然要把时间比较紧的先安排了。所以先按扣分的高低，由高向低排序，如果两门课扣分相同就按他们的结束时间由低向高排序！然后安排即可！

[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;  

}  

 

补充：软件开发 , C++ ,