慢慢来，沉稳一点。
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
&v){ sort(v.begin(), v.end()); int ans = 0; int flag[100];//确保足够长的时间 int len = v.size(); memset(flag, 0, sizeof(flag)); //将flag定义成vector初始化为0也行 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
#include #include #include 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 &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 res; for(int i = 0; i < t; i++){ int n; cin>>n; vector v; vector Deadline; vector 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<<"第"< 4. 运行结果