Week4：DDL的恐惧——贪心
题目内容
ZJM 有 n 个作业，每个作业都有自己的 DDL，如果 ZJM 没有在 DDL 前做完这个作业，那么老师会扣掉这个作业的全部平时分。
所以 ZJM 想知道如何安排做作业的顺序，才能尽可能少扣一点分。
输入格式
输入包含T个测试用例。输入的第一行是单个整数T，为测试用例的数量。
每个测试用例以一个正整数N开头(1<=N<=1000)，表示作业的数量。
然后两行。第一行包含N个整数，表示DDL，下一行包含N个整数，表示扣的分。
输出格式
对于每个测试用例，您应该输出最小的总降低分数，每个测试用例一行。
输入示例
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
输出示例
0
3
5
示例解释
上方有三组样例。
对于第一组样例，有三个作业它们的DDL均为第三天，ZJM每天做一个正好在DDL前全部做完，所以没有扣分，输出0。
对于第二组样例，有三个作业，它们的DDL分别为第一天，第三天、第一天。ZJM在第一天做了第一个作业，第二天做了第二个作业，共扣了3分，输出3。
解题思路
这道题是一道简单的贪心。
首先在输入的时候保存好所有DLL里最晚(大)的一个，即最大时间maxtime。
然后预处理：
- 对所有的作业进行排序
- 优先按照分数排列，分数比较大的排在前面
- 如果分数一样，那当然就是先完成DDL早的啦(即DDL小的排在前面)
接下来对每个作业都顺着时间走一遍。
如果遇到的当前时间满足：
- 当前这一天没有其他的作业占着了
- 在此基础上，这项作业的DDL还没到截止日期(即ddl比当前时间小)
那么就设置当前时间点被作业“占据”(visit数组)，然后跳出当前点对时间表的遍历，继续下一个点的遍历。
如果当前点没能找到一个拿来写这项作业的日子，那么就得扣这个分。
最后输出整个过程下来扣的所有的分就可以了。
AC代码
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>using namespace std;struct DDL
{int time;int score;DDL(int t, int s = 0){time = t;score = s;}
};bool cmp(const DDL& a, const DDL& b)
{if (a.score != b.score) return a.score > b.score;else return a.time < b.time;
}vector<DDL>tasks;
int timetable[50000];int main()
{int T, n;cin >> T;while (T--){cin >> n;memset(timetable, 0, sizeof(timetable));tasks.clear();int temp;int maxtime = -1;for (int i = 0; i < n; i++){ cin >> temp;tasks.push_back(DDL(temp));maxtime = max(maxtime, temp);}for (int i = 0; i < n; i++){cin >> temp;tasks[i].score = temp;}sort(tasks.begin(), tasks.end(), cmp);int sum = 0;for (int i = 0; i < tasks.size(); i++)//遍历点{bool isok = false;for (int t = maxtime; t > 0; t--)//遍历时间表{if (timetable[t]) continue;else{if (tasks[i].time < t) continue;else{timetable[t] = 1;isok = true;break;}}}if (!isok) sum += tasks[i].score;}cout << sum << endl;}
}
发布评论