DDL-贪婪算法

DDL问题

问题描述

有 n 个作业，每个作业都有自己的 DDL，如果没有在 DDL 前做完这个作业，那么老师会扣掉这个作业的全部平时分。如何安排做作业的顺序，才能尽可能少扣一点分？

Input

输入包含 T 个测试用例。输入的第一行是单个整数 T，为测试用例的数量。
每个测试用例以一个正整数 N 开头(1 ≤ N ≤ 1000)，表示作业的数量。
然后两行。第一行包含 N 个整数，表示 DDL，下一行包含 N 个整数，表示扣的分。

Output

对于每个测试用例，您应该输出最小的总降低分数，每个测试用例一行。

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
Output: 
0
3
5

Limitation

Time limit		1000 ms
Memory limit	32768 kB

解题思路

将扣的分数降序排列，第二关键字按DDL降序排列，然后按照时间线从后往前遍历，并用reach数组标记当天是否被其他作业占用，这样可以保证被扣的分最少，因为每次都优先安排分值大的，且从最晚的DDL往较近的日子安排，这样可以保证后面的晚的DDL对早的DDL的影响最小。

收获

对于时间，我们总是思维定式从前往后，然而本题将时间“倒流”求解，容易得出答案。(助教课上如果没说的话我还真不会往这方面思考🤯)

源代码

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

struct score {
	int ddl;//due
	int s;//due后扣的分
	score(){ }
	score(int _ddl, int _s) :ddl(_ddl), s(_s) {  }
	bool operator > (const score sc)const {
		if (s == sc.s)
			return ddl > sc.ddl;
		return s > sc.s;
	}
};

bool cmp(score a, score b) {
	return a > b;
}

int result(score* ddl, int n) {
	int reach[10000];//标记在哪天是否做了作业
	memset(reach, 0, 10000);
	int sum = 0;
	for (int i = 0; i < n; i++) {
		int x = ddl[i].ddl;

		bool setdown = false;//标记某作业是否完成
		while (x > 0) {//从第x天(也就是DDL)开始安排 可安排就安置
			if (reach[x] == 0) {//有空
				reach[x] = 1;//占用当天
				setdown = true;//做了这个作业
				break;
			}
			x--;//不然继续往前一天看看是否可安排
		}
		if (setdown == false)//若前面这些天都被占用了
			sum += ddl[i].s;//无法完成作业 扣分
	}
	return sum;
}

int main() {
	int t;
	cin >> t;//t组数据
	for (int i = 0; i < t; i++) {
		int n;
		cin >> n;//n个DDL
		int* arr1 = new int[n + 5];
		int* arr2 = new int[n + 5];
		for (int j = 0; j < n; j++)
			cin >> arr1[j];//DDL
		for (int j = 0; j < n; j++)
			cin >> arr2[j];//分

		score* DDL = new score[n + 10];
		for (int j = 0; j < n; j++) {//整理DDL跟分 存入结构体方便记录
			score sc(arr1[j], arr2[j]);
			DDL[j] = sc;
		}
		sort(DDL, DDL + n, cmp);//按扣的分数降序 第二关键字按DDL降序
		cout << result(DDL, n) << endl;//丢入函数处理
	}

	return 0;
}