题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1789
本题的目的是制定一个写作业的顺序，使得最后被扣的分数最少，最后输出最少的扣分数。要想扣分少，就必须优先考虑分值大的家庭作业。因此采用贪心策略比较合适，优先将分值大的作业先做完，剩下做不完的作业加起来自然是最小的。这里的做法是先按照家庭作业的分值大小进行降序排序，然后遍历在决策哪天做哪门作业。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define N 1005 6 //标志数组，表示第i天有是否处于空闲状态 7 bool flag[N]; 8 //定义homework结构体 9 struct task{ 10 //d 截止日期 11 //s 分值 12 //isdone 有没有被完成 13 int d,s; 14 bool isdone; 15 }; 16 //存储 家庭作业 17 task T[N]; 18 bool DESC(task t1,task t2){ 19 return t1.s>t2.s; 20 } 21 int main(){ 22 int n; 23 cin>>n; 24 while(n--){ 25 //将flag数组重置 26 memset(flag,false,sizeof(flag)); 27 int m=0; 28 cin>>m; 29 //将homework存入数据结构中 30 for(int i=1;i<=m;i++){ 31 cin>>T[i].d; 32 T[i].isdone=false; 33 } 34 for(int i=1;i<=m;i++) 35 cin>>T[i].s; 36 //按照作业的分值大小降序排序 37 sort(T+1,T+m+1,DESC); 38 //贪心算法 39 //优先考虑分值大的家庭作业 40 //如果截止日期那天没有要做的作业，则将该作业计划在那天做 41 //否则从截止日期往前推，直到发现空闲的一天 42 for(int i=1;i<=m;i++){ 43 for(int j=T[i].d;j>0;j--) 44 if(flag[j]==false){ 45 flag[j]=true; 46 T[i].isdone=true; 47 break; 48 } 49 } 50 //计算未完成的作业所造成的扣分值 51 int result=0; 52 for(int i=m;i>0;i--){ 53 if(T[i].isdone==false) 54 result+=T[i].s; 55 } 56 cout<<result<<endl; 57 } 58 return 0; 59 }