双机流水作业调度问题（Johnson算法）

问题定义:

双机流水作业调度：总共有n个作业，作业\(i\)分为两个内容，需要按顺序先后在机器A和机器B上完成，分别需要时间\(a_i,b_i\)来完成，一台机器只能同时进行一项作业，问完成所有作业所需的最小时间。

多机流水作业调度：一个作业需要在大于两台机器上先后完成，是NP-hard问题。

解法：

问题就是求最佳作业序列。设前i项作业所需的时间为\(C_i\)，可以得出以下式子

\[c_{i}=\left\{\begin{array}{ll}a_{1}+b_{1} & , i=1 \\\max \left\{c_{i-1}, \sum_{j=1}^{i} a_{j}\right\}+b_{i} & , 2 \leq i \leq n\end{array}\right. \]

可以证明，对于相邻两项i和j，如果\(min(a_i,b_j)<min(a_j,b_i)\)则i项放前面更优。

将\(a_i\)和\(b_i\)的关系分为<,=,>三类，可以得到如下排列顺序:

1.当 \(a_{i}<b_{i}, a_{j}<b_{j}\) 时， \(a_{i} \leq a_{j},\) 应该按a升序排序
2.当 \(a_{i}=b_{i}, a_{j}=b_{j}\) 时，随意排列。
3.当 \(a_{i}>b_{i}, a_{j}>b_{j}\) 时， \(b_{i} \geq b_{j},\) 应该按b降序排序。

同样可以证明，\(a_i<b_i\)的项应该排在最前，然后是\(a_i=b_i\)的项，最后是\(a_i>b_i\)的项。

代码:

//P1248，给定n，ai,bi，求最小用时和对应序列
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
struct node{
    int a,b,d,id;
    bool operator<(const node &v)const {
        if(d!=v.d)return d<v.d;
        else if(d==-1){
            return a<v.a;
        }
        else{
            return b>v.b;
        }
    }
}p[maxn];
int main () {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&p[i].a);
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i].b);
        p[i].id=i;
        int cha=p[i].a-p[i].b;
        if(cha==0)p[i].d=0;
        else p[i].d=cha<0?-1:1;
    }
    sort(p+1,p+1+n);
    ll ans=0,dt=0;
    for(int i=1;i<=n;i++){
        ans+=p[i].a;
        dt=max(0ll,dt-p[i].a);
        dt+=p[i].b;
    }
    ans+=dt;
    printf("%lld\n",ans);
    for(int i=1;i<=n;i++){
        if(i>1)printf(" ");
        printf("%d",p[i].id);
    }
    puts("");
}