1 条题解

  • 0
    @ 2024-10-29 10:09:39

    解析:要想总时间最短,就尽量让两个车间的等待时间最短。 将这些任务排序,若A车间时间小于B车间时间,A车间时间短的排前面,若A车间时间大于B车间时间,B时间长的排前面。

    #include <bits/stdc++.h>
    using namespace std;
    int n;
    struct node {
        int a;//A车间的加工时间
        int b;//B车间的加工时间
        int id;
    };
    node a[10005];
    bool cmp(node x,node y){
        if (x.a>=x.b&&y.a>=y.b){//若A车间的时间都大于B车间时间
            return x.b>y.b;//B车间时间长的排前面
        }else if (x.a<x.b&&y.a<y.b){//若A车间时间都小于B车间时间
            return x.a<y.a;//A车间时间短的排前面
        }else{//一个A车间时间大于B车间时间,另一个A车间时间小于B车间时间
            return x.a<x.b;//A车间时间小于B车间时间的排前面
        }
    }
    int main() {
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i].a;
        }
        for(int i=1;i<=n;i++){
            cin>>a[i].b;
            a[i].id=i;
        }
        sort(a+1,a+n+1,cmp);//排序
        int ta=0,tb=0;//A车间用时,B车间用时
        //模拟加工n个
        for(int i=1;i<=n;i++){
            ta+=a[i].a;
            tb=max(tb,ta);//若当时A车间未加工完,要等A车间加工完
            tb+=a[i].b;
        }
        cout<<tb<<endl;//B车间的总用时
        for(int i=1;i<=n;i++){//输出加工顺序
            cout<<a[i].id<<" ";
        }
        return 0;
    }
    • 1

    信息

    ID
    609
    时间
    1000ms
    内存
    512MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者