做散热网站,地方门户网站有哪些,涿鹿镇做网站,国家企业信息网官网查询营业执照慢慢来#xff0c;沉稳一点。
2024年6月18日 题目描述 A同学有n份作业要做#xff0c;每份作业有一个最后期限#xff0c;如果在最后期限后交作业就会扣分#xff0c;现在假设完成每份作业都需要一天。A同学想安排作业顺序#xff0c;把扣分降到最低#xff0c;请帮他实…慢慢来沉稳一点。
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初始化为falseans表示扣分初始化为0
i 0时其截至时间为4选择在第4天完成该作业days[4] true不用惩罚ans 0i 1时其截至时间为2选择在第2天完成该作业days[2] true不用惩罚ans 0i 2时其截至时间为4第4天已经规划做作业0了那就提前一天选择在第3天完成该作业days[3] true不用惩罚ans 0i 3时其截至时间为3第3天已经规划做作业2了如果提前一天第二天同样也安排了做作业1那就提前两天days[1] true不用惩罚ans 0i 4时其截至时间为1从前面看来前四天都安排了任务尽可能地做扣分大的了那么当前就不能完成该作业了需要惩罚ans 3i 5时其截至时间为4和作业4相同情况没有可以安排的时间了需要惩罚ans 32 5i 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(vectorhomework 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. 完整代码如下
// 带惩罚的调度问题#includeiostream
#includevector
#includecstring
#includealgorithmusing 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(vectorhomework 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;cint;vectorint res;for(int i 0; i t; i){int n;cinn;vectorhomework v;vectorint Deadline;vectorint Punish;// 输入数据for(int i 0; i n; i){int deadline;cindeadline;Deadline.emplace_back(deadline);}for(int i 0; i n; i){int punish;cinpunish;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. 运行结果
