贪心算法——赶作业（C++）

慢慢来，沉稳一点。

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);}// 初始化homeworkfor(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
// 5

4. 运行结果