A-DDL的恐惧

题目描述

ZJM 有 n 个作业，每个作业都有自己的 DDL，如果 ZJM 没有在 DDL 前做完这个作业，那么老师会扣掉这个作业的全部平时分。
所以 ZJM 想知道如何安排做作业的顺序，才能尽可能少扣一点分。
请你帮帮他吧！

Input:输入包含T个测试用例。输入的第一行是单个整数T，为测试用例的数量。
每个测试用例以一个正整数N开头(1<=N<=1000)，表示作业的数量。
然后两行。第一行包含N个整数，表示DDL，下一行包含N个整数，表示扣的分。
Output:对于每个测试用例，您应该输出最小的总降低分数，每个测试用例一行。
Exmaple:
Sample Input:
3
3
3 3 3
10 5 1
3
1 3 1
6 2 3
7
1 4 6 4 2 4 3
3 2 1 7 6 5 4
Sanmple Output:
0
3
5

题目思路

这道题我们最开始能想到的是贪心算法，贪心准则是ddl的分数，因为我们需要安排ddl使得得分最多，所以我们要尽可能多得安排分数较高的ddl。这里我们根据输入的数据对ddl的分数降序排序。另外使用一个bool类型的t数组表示某天是否安排了ddl。在已经排好序的ddl数组中，依次查看这个任务可不可以安排在ddl之前的时间里，即查看t数组，如果可以则将这个任务的分数加到sum2中，并且改变t数组该天的值。

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10000;

struct DDL{
	int point;
	int time;
	
	bool operator < (const DDL& s)const{
		return point > s.point;		//按ddl的分数降序排列 
	}
}ddl[N];
bool t[N];

int main()
{
	int T;
	cin >> T;
	for(int i = 0; i < T; i++)
	{
		int n;
		cin >> n;
		int sum1 = 0;
		for(int j = 0; j < n; j++)
			cin >> ddl[j].time;
		for(int j = 0; j < n; j++)
		{
			cin >> ddl[j].point;
			sum1 += ddl[j].point;
		}
			
		sort(ddl , ddl + n);
		int a = 0;
		int sum2 = 0;
		memset(t , false , sizeof(t));		//初始化数组
		while(a < n)
		{
			for(int j = ddl[a].time; j > 0; j--)
			{
				if(!t[j])
				{
					sum2 += ddl[a].point;
					t[j] = true;
					break;
				}
			}
			a++;
		}
		cout << sum1 - sum2 << endl;	
	}
	return 0;
 } 

总结

在这里我们使用了一个bool类型的数组用来记录每天是否安排了任务，这样可以方便实现。在这个数组的初始化上我使用了包含在“cstring”头文件中的memset函数。