(hdu step 9.1.2)Doing Homework again(贪心——有n份作业,每份作业都有一定的完成时间及没有完成时需要付出的代价,求最小代价)

题目：

333 3 310 5 131 3 16 2 371 4 6 4 2 4 33 2 1 7 6 5 4

题目分析：

               贪心。贪心策略为：如果完成时间不同，完成时间紧迫的排在前面。如果完成时间相同,那么付出代价大的排在前面。其实到这里，只是保证了完成的作业书尽可能的多，但是，并没有保证付出的代价最小。当一份作业可能不能完成时，我们需要在前面寻找一份代价比当前作业不做所付出的代价要小的作业舍弃掉。

代码如下：

/*
 * b.cpp
 *
 *  Created on: 2015年3月26日
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>
#include <algorithm>


using namespace std;

const int maxn = 1001;

struct Homework{
	int deadline;
	int score;
	bool flag;
}homeworks[maxn];

bool cmp(Homework a,Homework b){
	if(a.deadline != b.deadline){//如果作业的完成时间不同
		return a.deadline < b.deadline;//那么完成时间紧迫的作业排在前面
	}

	return a.score > b.score;//如果完成时间相同,那么没完成时扣掉的分数多的排在前面
}


int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);

		int i;
		for(i = 0 ; i < n ; ++i){//依次读入每个作业的完成时间
			scanf("%d",&homeworks[i].deadline);
		}

		for(i = 0 ; i < n ; ++i){//一次读入每个作业没完成所需要付出的代价
			scanf("%d",&homeworks[i].score);
			homeworks[i].flag = true;//所有的作业一开始默认都是可以完成的
		}

		sort(homeworks,homeworks+n,cmp);//将作业按照优先级进行排序

		int k = 1;//当前天数
		int sum = 0;//所需要付出的代价
		for(i = 0 ; i < n ; ++i){//遍历所有的作业
			if(homeworks[i].deadline >= k){//如果当前作业的完成时间在当前天数的后面
				k++;//那么证明当前作业可以完成
				continue;//寻找下一个作业
			}
			//以下代码可以执行,佐鸣找到了一份不能完成的作业

			int p = homeworks[i].score;//标记没完成当前这份作业所需要付出的代价
			int pos = i;//标记当前作业的索引
			int j;
			//寻找一份作业,该作业如果不做的话,所付出的代价最小
			for(j = 0 ; j < i ; ++j){//遍历改作业之前的左右作业
				//如果找到一份作业如果不做的话,付出的代价<当前作业不做所付出的代价的话 && 该作业被做了
				if(homeworks[j].score < p && homeworks[j].flag == true){
					p = homeworks[j].score;//更新当前需要付出的代价
					pos = j;//记录该作业的索引
				}
			}

			sum += p;//将总代价 加上被舍弃掉的作业所需要付出的代价
			homeworks[pos].flag = false;//将该作业标记为未完成(被舍弃掉)
		}

		printf("%d\n",sum);
	}

	return 0;
}