[Johnson法则]

P1248

加工生产调度

求一个加工顺序，使得加工时间最短，就要让机器的空闲时间最短，A一旦开始加工就要不停地加工，但加工过程中存在A机器会等待B机器加工，B机器也要等待A机器加工。很明显A机器的第一个工件，B机器必须要等待，B机器的最后一个工件，A机器必须要等待。所以要让\(a_i\)小的在A先加工，让\(b_i\)大的在B先加工。令\(m_i\)表示\(min(a_i,b_i)\)然后从小到大排序\(m_i\)，令\(ans[i]\)表示最终工件的加工顺序，接着从\(1~n\)循环，如果\(m_i=a_i\),让\(head++,ans[head] = a_i\)的位置，否则\(tail--,ans[tail] = b_i\)的位置。代码如下

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2005;
int n,a[maxn],b[maxn];
int head,tail,ans[maxn];
int time_a,time_b;
struct qwq{
    int mini,pos;
    bool operator < (const qwq &x)const
    {
        return mini < x.mini;
    }
}e[maxn];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
    {
        e[i].mini = min(a[i],b[i]);
        e[i].pos = i;
    }
    sort(e+1,e+n+1);
    tail = n + 1;
    for(int i=1;i<=n;i++)
    {
        if(e[i].mini == a[e[i].pos])
        {
            head ++;
            ans[head] = e[i].pos;
        }
        else
        {
            tail --;
            ans[tail] = e[i].pos;
        }
    }
    for(int i=1;i<=n;i++)
    {
        time_a += a[ans[i]];
        if(time_b < time_a)
            time_b = time_a;
        time_b += b[ans[i]];
    }
    printf("%d\n",time_b);
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}