「一本通 1.1 例 4」加工生产调度

https://loj.ac/problem/10003

Analysis

因为B一定要在A之后才可以进行，所以总时间最小的话要先把需要A和需要B的小的时间放到最前面，然后使用双指针： 如果是A那么从前往后排序 如果是B那么从后往前排序

Code

#include <bits/stdc++.h>

using namespace std;

struct point {
    int i, minn, x, y;
};

point a[1010];
int ans[1010];
const int inf = 0x3f3f3f3f;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].x;
    for (int i = 1; i <= n; ++i) cin >> a[i].y;
    for (int i = 1; i <= n; ++i) {
        a[i].minn = min(a[i].x, a[i].y); // find the min
        a[i].i = i;
    }
    sort(a + 1, a + n + 1, [](const point& l, const point& r) { return l.minn < r.minn; });
    int x = 1, y = n;
    for (int i = 1; i <= n; ++i) {
        if (a[i].minn == a[i].x) // A should finish first
            ans[x++] = a[i].i;
        else
            ans[y--] = a[i].i;
    }
    int timea = 0, timeb = 0, mina = inf, minb = inf;
    for (int i = 1; i <= n; ++i) {
        timea += a[i].x;
        timeb += a[i].y;
        mina = min(mina, a[i].x);
        minb = min(minb, a[i].y);
    }
    cout << max(timea + minb, timeb + mina) << endl;
    for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
    return 0;
}

---

Last update: January 9, 2021