题解 P1248 【加工生产调度】

Celtic · 2020-02-24 11:19:36 · 题解

要使时间最短，则就是让机器的空闲时间最短。 A 机器在加工过程中，有可能要等待 A 机器。 最后一个部件在 B 机器上加工， A 机器也在等待 B 机器的完工。

要使总的空闲时间最少，就要把在 A 机器上加工时间最短的部件最先加工，这样使得 B 机器能以最快的速度开始加工；把在 B 机器上加工时间最短的部件放在最后加工。这样使得 A 机器能尽快的等待 B 机器完工。

于是我们可以设计出这样的贪心法：

设 M_i=min(a_i,b_i) 将 M 按照从小到大的顺序排序。然后从第 1 个开始处理，若M_i=a_i，则将它排在从头开始的作业后面，若M_i=b_i，则将它排在从尾开始的作业前面。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 2001001
#define re register 
#define eps 1e-10 
#define MAX 2001
using namespace std; 
typedef long long ll; 
typedef double db;
inline void read(re ll &ret) 
{ 
    ret=0;re ll pd=0;re char c=getchar(); 
    while(!isdigit(c)){if(c=='-')pd=1;c=getchar();} 
    while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c^48);c=getchar();} 
    ret=pd?-ret:ret; 
}
ll n,ans[N];
struct cow
{
    ll a,b,data;
    inline friend bool operator <(re cow x,re cow y)
    {
        return min(x.a,y.b)<min(x.b,y.a);
    }
}c[N];
int main() 
{
    read(n);
    for(re int i=1;i<=n;i++)
    {
        read(c[i].a);
        c[i].data=i;
    }
    for(re int i=1;i<=n;i++)
        read(c[i].b);
    sort(c+1,c+n+1);
    re ll now1=0,now2=0;
    for(re int i=1;i<=n;i++)
    {
        now1+=c[i].a;
        now2=now2>now1?now2:now1;
        now2+=c[i].b;
    }
    printf("%lld\n",now2);
    for(re int i=1;i<=n;i++)
        printf("%lld ",c[i].data);
    exit(0);
}