在我上一篇说到的,就是这个,贪心的做法,对比一下就能发现,另一个的扣分会累加而且最后一定是把所有的作业都做了,而这个扣分是一次性的,所以应该是舍弃扣分小的,所以结构体排序后,往前选择一个损失最小的方案直接交换就可以了.
#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; struct HomeWork { int deadline; int reduce; } hw[1005]; bool mark[1005]; int t; int n; int search(HomeWork a[],int x,int len) { int i,pl=-1,min=x; for(i=0; i<len; i++) if(mark[i]==true&&a[i].reduce<min) { min=a[i].reduce; pl=i; } return pl; } bool cmp(HomeWork a ,HomeWork b) { if(a.deadline!=b.deadline) return a.deadline<b.deadline; else return a.reduce>b.reduce; } int main() { scanf("%d",&t); while(t--) { memset(mark,0,sizeof(mark)); memset(hw,0,sizeof(hw)); int i; scanf("%d",&n); for(i=0; i<n; i++) scanf("%d",&hw[i].deadline); for(i=0; i<n; i++) scanf("%d",&hw[i].reduce); sort(hw,hw+n,cmp); int day=0,reduced=0,tmp; for(i=0; i<n; i++) { if(day<hw[i].deadline) { day++; mark[i] = true; } else { int ex = search(hw,hw[i].reduce,i); if(ex!=-1) { tmp=hw[ex].reduce; hw[ex].reduce = hw[i].reduce; hw[i].reduce=tmp; } reduced += hw[i].reduce; } } printf("%d\n",reduced); } return 0; }
原文：http://www.cnblogs.com/jifahu/p/5449626.html