加工生产调度 题解

简洁题意

n个产品要分别在 A、B 两个车间加工．每个作业i必须先在 A 上然后在 B 上加工，时间分别为 和。而你需要确定这n个产品的加工顺序，使得从第一个任务开始在 A 上加工到最后一个任务在 B 上加工完成的总时间尽量小。

Solution

很容易知道最优调度一定让 A 没有空闲(或者说，空闲全部在等 B 工作)，B的空闲时间尽量少。

算法:（我语言不是特别优美，还是放一下 cmp 函数）

bool cmp(Work_Johnson a, Work_Johnson b)
{
    if (a.MinNum == Int_B) {
        if (b.MinNum == Int_A) {
            return false;
        }
        else {
            return a.minab > b.minab;
        }
    }
    else {
        if (b.MinNum == Int_B) {
            return true;
        }
        else {
            return a.minab < b.minab;
        }
    }
}

MinNum : 小还是 小
minab:

程序易于实现，复杂度O(nlogn) 【主要在排序上】

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <math.h>
#include <queue>
#include <vector>
#define ll long long
#define Inf 0x3f3f3f3f
#define pow2(a) (a) * (a)
#define Char_Int(a) ((a) & 15)
#define Int_Char(a) ((a) + '0')
#define Pi 3.141592653589793
using namespace std;

ll readint();
void writeint(int); 

//#define DUIPAI
//#define BIGOUT
//#define DEBUG

const int Int_A = 0;
const int Int_B = 1;

struct Work_Johnson {
    int a, b;
    int minab, MinNum;
    int ptr;
    inline void Read_A()
    {
        //Read Optimize A
        register char t_ch;
        t_ch = getchar();
        while (t_ch > '9' || t_ch < '0') t_ch = getchar();
        a = Char_Int(t_ch);
        while ((t_ch = getchar()) <= '9' && t_ch >= '0') 
            a = (a << 3) + (a << 1) + Char_Int(t_ch);
    }
    inline void Read_B()
    {
        //Read Optimize B
        register char t_ch;
        t_ch = getchar();
        while (t_ch > '9' || t_ch < '0') t_ch = getchar();
        b = Char_Int(t_ch);
        while ((t_ch = getchar()) <= '9' && t_ch >= '0') 
            b = (b << 3) + (b << 1) + Char_Int(t_ch);
    }
    inline void SetMin()
    {
        if (a < b) {
            minab = a;
            MinNum = Int_A;
        }
        else {
            minab = b;
            MinNum = Int_B;
        }
    }
    inline bool operator < (Work_Johnson &other) const
    {
        return minab < other.minab;
    }
    inline bool operator > (Work_Johnson &other) const
    {
        return minab > other.minab;
    }
    inline bool operator <= (Work_Johnson &other) const
    {
        return !(minab > other.minab);
    }
    inline bool operator >= (Work_Johnson &other) const
    {
        return !(minab < other.minab);
    }
    inline bool operator == (Work_Johnson &other) const
    {
        return !(minab > other.minab) && !(minab < other.minab);
    }
    inline bool operator != (Work_Johnson &other) const
    {
        return (minab > other.minab) || (minab < other.minab);
    }
};

bool cmp(Work_Johnson a, Work_Johnson b)
{
    if (a.MinNum == Int_B) {
        if (b.MinNum == Int_A) {
            return false;
        }
        else {
            return a.minab > b.minab;
        }
    }
    else {
        if (b.MinNum == Int_B) {
            return true;
        }
        else {
            return a.minab < b.minab;
        }
    }
}

int main()
{
    int n = readint();
    Work_Johnson *wj = new Work_Johnson[n];
    for (int i = 0; i < n; i++) {
        wj[i].ptr = i;
    }
    for (int i = 0; i < n; i++) {
        wj[i].Read_A();
    }
    for (int i = 0; i < n; i++) {
        wj[i].Read_B();
    }
    for (int i = 0; i < n; i++) {
        wj[i].SetMin();
    }
    sort(wj, wj + n, cmp);    
    int JGa = 0, JGb = 0;
    for (int i = 0; i < n; i++) {
        JGa += wj[i].a;
        if (JGb < JGa) JGb = JGa;
        JGb += wj[i].b;
    } 

    printf("%d\n", JGb); 
    for (int i = 0; i < n; i++) {
        printf("%d ", wj[i].ptr + 1);
    } 
    return 0;
} 

inline ll readint()
{
    char c = getchar();
    while (c > '9' || c < '0' && c != '-') c = getchar();
    //if (c == '-') flag = -1, c = getchar();
    ll init = Char_Int(c);
    while ((c = getchar()) <= '9' && c >= '0') init = (init << 3) + (init << 1) + Char_Int(c);
    return init/* * flag*/;
}

inline void writeint(int x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) writeint(x / 10);
    putchar(Int_Char(x % 10));
}