P1248 加工生产调度

贪心。
###一、主算法

• 此题用贪心（很明显这个没必要$DP$吧...这个全局最优每一步一定是最优的阿
• 考虑两个零件$i,j$
  有以下情况：
  1.先生产$i$:$T=T_{start}+a_i+max(a_j,b_i)+b_j$
  2.先生产$j$:$T=T_{start}+a_j+max(a_i,b_j)+b_i$
• 此时神奇的$Ac$想到了如下算法：
  根据此规则，对$a$数组进行排序，即：

  sort(a+1,a+n+1,cmp);
  

  其中此规则在$cmp$中有所体现（即$cmp$中就是按照这个来决定$i,j$的前后顺序的）
• 不愧是$Ac$,他水过去了！
• 但是据题解，这种算法是错的，然而尴尬的是我也不知道为什么是错的阿

###二、正解（$Byz$)
我来为某威代言了

• 排序方式
  
  这里解释下，以$d$为关键字排序即最终顺序依次是$a_i<b_i$，$a_i=b_i$，$a_i>b_i$
  放个小小的$cmp$:

  inline int cmp(Node x,Node y){
    if(x.c!=y.c)
       return x.c<y.c;
    if(x.c!=1)
        return x.a<y.a;
    return x.b>y.b;
  }
  

• 为什么这么排序呢？
  因为你要使得总时间最小，$a$机器工作的时间一定是固定的，那么就要让$b$等待的时间尽量的小
• 这里举一个例子，如果有两个东西分别是$5,2$和$3,6$
  先做第一个的话耗时$T=5+3+6=14$
  先做第二个的话耗时$T=3+6+2=11$
  现在应该很好理解为什么$a_i<b_i$的放在前面比较好了吧
  具体的证明就不证明了，感性理解下就是如果把$a_i<b_i$的放在前面可以让$a_i$结束时间尽可能的早，便于更快的生产$b_i$，尽可能少的出现过多的等待情况。
• 这就是所有题目的思路啦！后面的具体最小时间模拟即可，注意$T_b$的初始值阿。

###三、代码

#include <bits/stdc++.h>
#define ll long long
#define maxn 1001
using namespace std;
ll n,ta,tb;
struct Node{
    ll a,b,c,num;
}w[maxn];

inline ll read(){
    ll x=0,f=0;
    char c=getchar();
    while(!isdigit(c))
        f|=c=='-',c=getchar();
    while(isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline int cmp(Node x,Node y){
    if(x.c!=y.c)
       return x.c<y.c;
    if(x.c!=1)
        return x.a<y.a;
    return x.b>y.b;
}

int main(){
    n=read();
    for(register int i=1;i<=n;++i){
        w[i].a=read();
        w[i].num=i;
    }        
    for(register int i=1;i<=n;++i)
        w[i].b=read();
    for(register int i=1;i<=n;++i)
        if(w[i].a<w[i].b)
            w[i].c=-1;
        else if(w[i].a==w[i].b)
            w[i].c=0;
        else    
            w[i].c=1;
    sort(w+1,w+n+1,cmp);
    ta=w[1].a;
    tb=w[1].a+w[1].b;
    for(register int i=2;i<=n;++i){
        tb=max(ta+w[i].a,tb)+w[i].b;
        ta+=w[i].a;
    }
    printf("%lld\n",tb);
    for(register int i=1;i<=n;++i)
        printf("%lld ",w[i].num);
}

小知识：又双叒叕$you\ shuang\ ruo\ zhuo$