慢慢来，沉稳一点。
2024年6月18日
题目描述
A同学有n份作业要做，每份作业有一个最后期限，如果在最后期限后交作业就会扣分，现在假设完成每份作业都需要一天。A同学想安排作业顺序，把扣分降到最低，请帮他实现。
输入格式
包含t个测试用例，第一行是单个整数t。每个测试用例以一个正整数n开头，表示作业的数量，然后是两行；第一行包含n个整数，表示作业的截至日期；下一行包含n个整数，表示作业未完成需要扣的分数。
输出格式
输出扣的最少分数即可。
输入样例：
2
3
3 3 3
10 5 1
7
1 4 6 4 2 4 3
3 2 1 7 6 5 4
输出样例：
0
5
题解思路
贪心法——带惩罚的调度问题
利用贪心思想，想让扣的分最低，肯定是先做那些扣分最多的作业，尽可能地保持剩下的作业即使没能完成也可以让扣的分最小化，那第一步就是对作业按扣的分数从大到小排序了，那下一步干什么呢？是不是需要确定做作业的顺序了。
如果你觉得有疑问，不是已经按惩罚大小排序了吗，那先把惩罚最大的做完不就行了？
NO！！！
如果你是学生，你一般来说都是什么时候完成作业的呢？
欸，知道了吧，是不是deadline呢？就算扣分很严重，我们依然保持在最后一天做完不就行了嘛，对吧。
贪心的关键就在这：在排序完之后，我们每次都在截至时间或者靠近截至时间的某个时间完成作业就OK了，这样既能保证扣分大的作业顺利完成，扣分小的作业也能尽可能的完成了。
那这样是不是就能保证扣的分最小呢？
（好好想想哦，后续我会更新这篇博客，添加证明，大家可以在提出自己的看法）
以上面的第个例子为例：
作业截至：1 4 6 4 2 4 3
惩罚分数：3 2 1 7 6 5 4
1. 按惩罚分数排序得到：
作业截至：4 2 4 3 1 4 6
惩罚分数：7 6 5 4 3 2 1
2. 下面用i表示当前的作业，days数组用于记录那一天做哪一样作业（days初始化为false），ans表示扣分（初始化为0）：
- i = 0时，其截至时间为4，选择在第4天完成该作业，days[4] = true，不用惩罚，ans = 0；
- i = 1时，其截至时间为2，选择在第2天完成该作业，days[2] = true，不用惩罚，ans = 0；
- i = 2时，其截至时间为4，第4天已经规划做作业0了，那就提前一天，选择在第3天完成该作业，days[3] = true，不用惩罚，ans = 0；
- i = 3时，其截至时间为3，第3天已经规划做作业2了，如果提前一天，第二天同样也安排了做作业1，那就提前两天，days[1] = true，不用惩罚，ans = 0；
- i = 4时，其截至时间为1，从前面看来前四天都安排了任务，尽可能地做扣分大的了，那么当前就不能完成该作业了，需要惩罚，ans = 3；
- i = 5时，其截至时间为4，和作业4相同情况，没有可以安排的时间了，需要惩罚，ans = 3+2 = 5；
- i = 6时，其截至时间为6，选择在第6天完成该作业，days[6] = true，不用惩罚，ans = 5；
这样写，你通透了吗？
代码实现
1. 定义homework结构体，利用在结构体里面重载函数完成排序；
struct homework{
int deadline;
int punish;
homework(int deadline, int punish):deadline(deadline), punish(punish) {}
bool operator<(const homework &s) const{
return punish >= s.punish;
}
};2. 定义贪心函数getMinLoss；
int getMinLoss(vector<homework> &v){
sort(v.begin(), v.end());
int ans = 0;
int flag[100];
int len = v.size();
memset(flag, 0, sizeof(flag));
for(int i = 0; i < len; i++){
if(flag[v[i].deadline] == 0){
flag[v[i].deadline] = 1;
}
else{
int tmp = v[i].deadline;
while(flag[tmp]){
tmp--;
}
if(tmp == 0){
ans += v[i].punish;
}
else{
flag[tmp] = 1;
}
}
}
return ans;
}3. 完整代码如下：
// 带惩罚的调度问题
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
struct homework{
int deadline;
int punish;
homework(int deadline, int punish):deadline(deadline), punish(punish) {}
bool operator<(const homework &s) const{
return punish >= s.punish;
}
};
int getMinLoss(vector<homework> &v){
sort(v.begin(), v.end());
int ans = 0;
int flag[100];
int len = v.size();
memset(flag, 0, sizeof(flag));
for(int i = 0; i < len; i++){
if(flag[v[i].deadline] == 0){
flag[v[i].deadline] = 1;
}
else{
int tmp = v[i].deadline;
while(flag[tmp]){
tmp--;
}
if(tmp == 0){
ans += v[i].punish;
}
else{
flag[tmp] = 1;
}
}
}
return ans;
}
int main(){
cout<<"开始输入数据！！！";
int t;
cin>>t;
vector<int> res;
for(int i = 0; i < t; i++){
int n;
cin>>n;
vector<homework> v;
vector<int> Deadline;
vector<int> Punish;
// 输入数据
for(int i = 0; i < n; i++){
int deadline;
cin>>deadline;
Deadline.emplace_back(deadline);
}
for(int i = 0; i < n; i++){
int punish;
cin>>punish;
Punish.emplace_back(punish);
}
// 初始化homework
for(int i = 0; i < n; i++){
v.emplace_back(homework(Deadline[i], Punish[i]));
}
// 将每次的结果插入结果集
res.emplace_back(getMinLoss(v));
}
// 打印结果
int count = 1;
for(auto e:res){
cout<<"第"<<count<<"次最多扣"<<e<<"分"<<endl;
count++;
}
return 0;
}
// 2
// 3
// 3 3 3
// 10 5 1
// 7
// 1 4 6 4 2 4 3
// 3 2 1 7 6 5 4
// 0
// 54. 运行结果
