加工生产调度

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1245 字

Johnson 法则分段排序后模拟求工期

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1425
// 题意：n 个产品都要先在 A 车间加工再到 B 车间，给出各产品在两车间的时间，求最短总工期及对应的加工顺序。
// 思路：Johnson 法则。
// 1. A 时间小于 B 时间的产品放前段，按 A 时间升序排。
// 2. 其余产品放后段，按 B 时间降序排。
// 3. 按排好的顺序模拟：累加 A 的完工时刻，B 的开始时刻取「自身在 A 完工」与「上一个在 B 完工」的较大者。
// 复杂度：O(n log n) 时间 / O(n) 空间
// 易错点：后段是按 B 时间降序排，写成升序就得不到最优顺序。
// 易错点：总工期是 B 车间的最后完工时刻，不是 A、B 两个车间时间之和。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    if(!(cin >> n)) return 0;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    vector<int> front, back;
    for(int i = 0; i < n; i++){
        if(a[i] < b[i]) front.push_back(i);
        else back.push_back(i);
    }
    sort(front.begin(), front.end(), [&](int x, int y){
        return a[x] < a[y];
    });
    sort(back.begin(), back.end(), [&](int x, int y){
        return b[x] > b[y];
    });
    vector<int> ord;
    for(int x : front) ord.push_back(x);
    for(int x : back) ord.push_back(x);
    long long ta = 0, tb = 0;
    for(int x : ord){
        ta += a[x];
        tb = max(tb, ta) + b[x];
    }
    cout << tb << "\n";
    for(int i = 0; i < n; i++){
        if(i) cout << " ";
        cout << ord[i] + 1;
    }
    cout << "\n";
    return 0;
}

加工生产调度

正文

一本通·提高篇的其它内容