贪心 Johnson算法

科技前沿 • 2025-01-06 22:58 • 阅读 54

大家好，我是讯享网，很高兴认识大家。

问题描述：洛谷P1248 加工生产调度

题面：

某工厂收到了 n 个产品的订单，这 n 个产品分别在 A、B 两个车间加工，并且必须先在 A 车间加工后才可以到 B 车间加工。

某个产品 i 在 A、B 两车间加工的时间分别为 Ai,Bi。怎样安排这 n 个产品的加工顺序，才能使总的加工时间最短。

这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在 A、B 两车间加工完毕的时间。

思路理解：

很容易想到说A车间最好一直开着，不要停下来，把所有前期工作全部做完，再去让B车间做事。

这样的方式一定会比A做完一个再让B做一个好很多，那么问题就出在A车间的加工顺序。

可以想到的是，

1，A车间一定是先结束的，然后B车间最少还需要再加工一件产品。而如果B车间刚好只剩一件产品要加工，那肯定是把B加工所需时间最少的留下来。

2，A车间一定是最先开始的，B车间要等A车间加工完才能加工，想让B车间等待时间比较短，A车间的第一件物体加工时间也应该尽量短。

但中间的物体的顺序依然是一个问题。

这里提供johnson算法：

将所有物品分为两类，一类是ai<=bi的，一类是ai>bi的

很容易想到说先完成第一类再完成第二类是比较好的选择，这样子B车间等待的时间就会比较短

而在第一类中，我们可以按照ai升序排列进行加工，这样保证了A车间能尽快提供物品到B车间

例如a1=10,b1=20,a2=30,b2=40,a3=50,b3=60

我们想让B车间尽早开始那就先加工1物品，同样的就会加工完1去加工2物品

而在第二类中，我们可以按照bi降序排列进行加工，这样最后的结束时间就会比较短

上代码：

#include<bits/stdc++.h> using namespace std; int n,x[1314],y[1314],tot1,tot2,t,ans,k; struct node{ int a,b,num; }f1[1314]; struct nodee{ int aa,bb,numm; }f2[1314]; bool cmp1(node xx,node yy) { return xx.a<yy.a; } bool cmp2(nodee xxx,nodee yyy) { return xxx.bb>yyy.bb; } int main() { cin>>n; for(int i=1;i<=n;++i) cin>>x[i]; for(int i=1;i<=n;++i) cin>>y[i]; for(int i=1;i<=n;++i) { if(x[i]<=y[i]) { f1[++tot1].a=x[i]; f1[tot1].b=y[i]; f1[tot1].num=i; } else { f2[++tot2].aa=x[i]; f2[tot2].bb=y[i]; f2[tot2].numm=i; } } sort(f1+1,f1+tot1+1,cmp1); sort(f2+1,f2+tot2+1,cmp2); for(int i=1;i<=tot1;++i) { k+=f1[i].a; if(ans<k) ans=k; ans+=f1[i].b; } for(int i=1;i<=tot2;++i) { k+=f2[i].aa; if(ans<k) ans=k; ans+=f2[i].bb; } cout<<ans<<endl; for(int i=1;i<=tot1;++i) cout<<f1[i].num<<" "; for(int i=1;i<=tot2;++i) cout<<f2[i].numm<<" "; return 0; }

讯享网

贪心 Johnson算法

相关推荐