【贪心】费用最少

题目描述：

小墨老师总是不及时做作业，所以他总有很多的作业要做。每个老师都给了他一个完成作业的最后期限，如果他超过期限交作业，老师就会在他的期末评价中扣分。假设做每一门作业总是要一天。小墨老师希望你能够帮助他安排做作业的一个顺序，以便能够被扣掉的分数最少。

输入格式

输入包含了多个测试用例。输入的第一行是一个整数T，代表测试用例的个数。接下来的就是T个测试用例的输入。每个测试用例都从一个正整数N(1≤N≤1000)开始，代表了作业的数目。接下来有2行。第一行包含N个整数，分别代表各个作业提交的最后期限；第二行也有N个整数，即对应于各个作业操过时间提交的扣分。

输出格式：

对每一个测试用例，应该在一行中输出最小的扣分数。

输入样例：

2

3

3 3 3

10 5 1

3

1 3 1

6 2 3

输出格式：

0

3

解题思路：

这道题主要是在合理的期限内做分数最高的作业，也就是对作业进行排序。优先扣的分数高的，在分数相同情况下选择期限最短的。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct homework{
	int endline;
	int score;
};
int cmp(homework h1,homework h2){
	if(h1.score!=h2.score){
		return h1.score>h2.score;
	} else {
		return h1.endline<h2.endline;
	}
}
int main() {
	int T,N;
	homework h[1001];
	int isHave[100001];//用于记录当天是否已有任务 
	cin>>T;
	while(T--){
		int num=0;//扣分总和 
		memset(isHave,0,sizeof(isHave));
		cin>>N;
		for(int i=0;i<N;++i)
			cin>>h[i].endline;
		for(int i=0;i<N;++i)
			cin>>h[i].score;
		sort(h,h+N,cmp);
		for(int i=0;i<N;++i){
			int flag=0;
			for(int j=h[i].endline;j>0;j--){
				if(!isHave[j]){
					flag=1;
					isHave[j]=1;
					break;
				}
			}
			if(!flag){
				num+=h[i].score;
			}
		}
		cout<<num<<endl;
	}
	return 0;
}