Luogu [P1248] 加工生产调度

题目链接

这个题可以贪心

我们首先想：对于所有产品，我们大致可以将其分为三类：

　　①.在A车间的时间要比B车间长。

　　②.两者一样。

　　③.在B车间的时间要比A车间长。

对于这三大类，怎么安排顺序？

可以看出，①类是消耗B车间任务，③类是给B车间增加任务。

我们想，要想时间最快，必须要尽可能的让AB两车间没有空闲的工作。如果我们将①放在了开头，而③放在了结尾，那必然会导致开始时B工作的时间断断续续，最后等A工作完了，B还剩下一大堆任务。

所以我们要尽可能的将③放在开始，①放在结尾，②安排在中间就可以（没有什么影响）。

三大类排好顺序后，我们再想每一类内部之间的顺序：

　　对于①：放在结尾执行，到最后必然A全部执行完毕，B还剩一点没执行（因为A最后执行的产品刚刚归入B类），那我们此时所消耗的时间就是最后产品的B车间时间，当然是越小越好，所以③类要按照B从大到小排。

　　对于②：好像既然放在了中间，就无所谓了。

　　对于③：同①理，放在开始执行，一开始必然第一个任务执行A时，B此时空着，那我们此时所消耗的时间就是开始产品的A车间时间，当然是越小越好，所以①类要按照A从小到大排。

然后从头到尾模拟一遍就行了。

代码：

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

int n;

struct qwq{

    int A;

    int B;

    int C;//看看这个零件属于哪一类

    int id;//此零件下标

}e[];

int cmp(qwq &a,qwq &b){

    if(a.C!=b.C)

        return a.C>b.C;

    else if(a.C==)

        return a.A<b.A;

    else if(a.C==-)

        return a.B>b.B;

    else

        return a.A<b.A;

}

inline int read(){

    int x=;

    char ch=getchar();

    while(ch<''||ch>'')

        ch=getchar();

    while(ch>=''&&ch<=''){

        x=(x<<)+(x<<)+(ch^);

        ch=getchar();

    }

    return x;

}

int Time_c,cha;

int main(){

    n=read();

    for(int i=;i<=n;i++)

        e[i].A=read(),e[i].id=i;

    for(int i=;i<=n;i++){

        e[i].B=read();

        e[i].C=((e[i].B-e[i].A) >=  ? ((e[i].B-e[i].A) >  ?  : ) : -);//三目运算符给任务分类

    }

    sort(e+,e+n+,cmp);

    for(int i=;i<=n;i++){//模拟

        Time_c+=e[i].A;

        cha=max(cha-e[i].A,);

        cha+=e[i].B;

    }

    cout<<Time_c+cha<<endl;

    for(int i=;i<=n;i++)

        printf("%d ",e[i].id);

    return ;

}