首页 / 算法 / 流水作业调度(贪心) Johnson算法
流水作业调度(贪心) Johnson算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了流水作业调度(贪心) Johnson算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1321字,纯文字阅读大概需要2分钟。
内容图文
![流水作业调度(贪心) Johnson算法](/upload/InfoBanner/zyjiaocheng/724/b5906db7c6894872b825c350c4637cf9.jpg)
某工厂收到了 n个产品的订单,这 n个产品分别在 A、B 两个车间加工,并且必须先在 A 车间加工后才可以到 B 车间加工。
某个产品 i在 A,B 两车间加工的时间分别为Ai,Bi 。怎样安排这 n个产品的加工顺序,才能使总的加工时间最短。
这里所说的加工时间是指:从开始加工第一个产品到最后所有的产品都已在 A,B 两车间加工完毕的时间。
边上代码边说
开始让第二台机器等的时间缩小
最后让第一台机器等的时间更小
#include<bits/stdc++.h> #define re return #define inc(i,l,r) for(int i=l;i<=r;++i) using namespace std; template<typename T>inline void rd(T&x) { char c;bool f=0; while((c=getchar())<'0'||c>'9')if(c=='-')f=1; x=c^48; while((c=getchar())>='0'&&c<='9')x=x*10+(c^48); if(f)x=-x; } int n,pos[1005]; struct node{ int id,atime,btime,mintime; bool operator<(node a)const { re mintime<a.mintime; } }pro[1005]; int main() { // freopen("in.txt","r",stdin); rd(n); inc(i,1,n) { rd(pro[i].atime); pro[i].id=i; //加编号,第二问 } inc(i,1,n) { rd(pro[i].btime); pro[i].mintime=min(pro[i].atime,pro[i].btime); //取ai和bi中较小值mi } sort(pro+1,pro+n+1); //通过mi由小到大排序 int l=1,r=n; inc(i,1,n) { if(pro[i].mintime==pro[i].atime) pos[l++]=i; //ai小的放在前面 else pos[r--]=i; //bi小的放在后面 } //模拟 int now=0,last=0; inc(i,1,n) { now+=pro[pos[i]].atime; last=max(last,now)+pro[pos[i]].btime; } printf("%d\n",last); inc(i,1,n-1) printf("%d ",pro[pos[i]].id); printf("%d",pro[pos[n]].id); re 0; }
内容总结
以上是互联网集市为您收集整理的流水作业调度(贪心) Johnson算法全部内容,希望文章能够帮你解决流水作业调度(贪心) Johnson算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。