题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1789 题目大意：一个美女回学校了，但是作业没有做。现在每一个老师都给她交作业的最后时间，而且每一天只能完成一个作业。如果没有在老师给的最后时间里完成作业，那么就会被罚学分。她想让你安排她的作业时间，让她的学分被罚的少一点。要是你做的好会有神秘大奖。 解题思路： 1、作业只要在最后时间之前完成就可以了，那么我们先按截止日期排升序，截止日期相同的被罚分数多的排在前面。 2、首先设置一个现在的日期为1，要是满足这个条件———截止日期大于或者等于现在日期的，我们不妨先标记要做这个作业，现在日期加1，要是不满足这个条件呢，我们就在这个作业的最后时间之前找一个被我们标记要做的被罚分数最小的作业。让这个作业去取代被罚分数最小的。但是不要忘记了这个作业的分数必须要大于最小分数啊。 3、最后我们就历遍整个数组，没有被我们标记要做的，就被罚咯。 我们以题目例子为例： 首先我们排序后就变成这个样子了 0 0 0 0 0 0 0//表示有没有被标记 1 2 3 4 4 4 6 3 6 4 7 5 2 1 第一天1>=1成立标记为要做 天数加加 1 0 0 0 0 0 0 第二天2>=2成立标记为要做 天数加加 1 1 0 0 0 0 0 第三天3>=3成立标记为要做 天数加加 1 1 1 0 0 0 0 第四天4>=4成立标记为要做 天数加加 1 1 1 1 0 0 0 第五天4>=5不成立 在前面找一个被标记要做的且减分最小的给替换，于是 第一天的就被替换掉了 最后就变成这样0 1 1 1 1 0 0 还是第五天 因为上面只是把第一天要写的作业换了一下天数不变 第五天4>=5不成立在前面找一个被标记的且分数最小的，然后发现第三天的最小，但是当前的分数比第三天的还要小那么跳过，标记不变。 第五天6>=5成立标记为要做 0 1 1 1 1 0 1 最后历遍数组标记为0的就是我没有做的 最后注意的地方就是换作业的时候一定要是换的被标记要做的不然就错了 ac代码：
#include<stdio.h> #include<algorithm> using namespace std; struct index{ int dl;//表示截止时间 int gr;//表示被罚分数 bool key;//标记是否被做 }; bool cmp(index a,index b) { if(a.dl==b.dl) return a.gr>b.gr; else return a.dl<b.dl; } int main() { int t,n,i,k,max; index s[1010]; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&s[i].dl); for(i=0;i<n;i++) scanf("%d",&s[i].gr); for(i=0;i<n;i++) s[i].key=false; sort(s,s+n,cmp); k=1;//当前时间 for(i=0;i<n;i++) { if(s[i].dl>=k){ s[i].key=true;//标记为做 k++; } else { int min=i; for(int j=0;j<i;j++) { //一定要保证两个条件同时满足 特别是找的要是被标记的 if(s[min].gr>s[j].gr&&s[j].key==true) min = j; } if(min!=i)//当前作业的被罚分数是否大于前面的分数 { s[i].key=true; s[min].key=false; } } } max=0; for(i=0;i<n;i++) { if(s[i].key==false) max+=s[i].gr; } printf("%d\n",max); } }