生产调度

题目描述

某工厂收到了$n$个产品的订单，这$n$个产品分别在 A、B 两个车间加工，并且必须先在 A 车间加工后才可以到 B 车间加工。 某个产品$i$在 A、B 两车间加工的时间分别为$A_i$，$B_i$​。怎样安排这$n$个产品的加工顺序，才能使总的加工时间最短。

输入格式

第一行仅1个整数n，表示产品的数量。 接下来一行n个整数是表示这n个产品在 A 车间加工各自所要的时间。 最后的n个整数是表示这n个产品在 B 车间加工各自所要的时间。

#include <bits/stdc++.h>

#define int long long

using namespace std;

typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5 + 5;

struct node {
    int a,b,id,d;
    bool operator<(node x)const {
        if(d==x.d) {
            if(d<=0)
                return a<x.a;
            else
                return b>x.b;
        }
        return d<x.d;
//        return min(a,x.b)<min(b,x.a);
    }
};
node nodes[MAXN];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t, n, m;
    cin >> t;
    for(int i=0; i<t; i++) {
        cin>>nodes[i].a;
        nodes[i].id=i+1;

    }
    for(int i=0;i<t;i++){
        cin>>nodes[i].b;
        nodes[i].d=(nodes[i].a-nodes[i].b);
        if(nodes[i].d>0) {
            nodes[i].d=1;
        } else if(nodes[i].d<0)
        nodes[i].d=-1;
    }

    stable_sort(nodes,nodes+t);
    int time1=0,time2=0;
    for(int i=0; i<t; i++) {
        time1+=nodes[i].a;
        time2=((time2<time1)?(time1):(time2));
        time2+=nodes[i].b;

    }
    cout<<time2<<'\n';
    for(int i=0;i<t;i++)cout<<nodes[i].id<<' ';
}