解题思路

这道题是Johnson双流水线调度算法的基础题。

本题是要求一个加工顺序使得总的加工时间最少，而要使加工时间最少，就是让各车间的空闲时间最少。一旦A车间开始加工，便会不停地进行加工(我们不要去管车间是否能够一直生产，因为他们有三班，可以24时间不停地运转)。关键是B车间在生产的过程中，有可能要等待A车间的初加工产品。很显然所安排的第一个产品在A车间加工时，B车间是要等待的，最后一个产品在B车间加工时，A车间已经完成了任务。

要使总的空闲时间最少：

（1）就要把在A车间加工时间最短的部件优先加工，这样使得B车间能以最快的速度开始加工；

（2）把放在B车间加工时间最短的产品放在最后加工，这样使得最后A车间的空闲时间最少。

#include 
    
     #define _for(i,a,n) for(int i=a;i
     
      >T;while(T--)#define close() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)typedef long long ll;template
      
       inline void read(T &x){bool Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}template
       
        inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}template
        
         inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}template
         
          inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}using namespace std;const int maxn = 1e3;struct node { int id; //工作编号 int t; //工作时间 int ab; //所属哪台机器 inline bool operator < (const node &b) const { return t < b.t; } node(int _id = 0,int _t = 0,int _ab = 0):id(_id), t(_t), ab(_ab){} }arr[maxn + 5];int n, a[maxn + 5], b[maxn + 5], ans[maxn + 5], ti[maxn + 5];void Johnson(){ rep(i, 1, n) { if(a[i] < b[i]) arr[i] = node(i, a[i], 0); else arr[i] = node(i, b[i], 1); } sort(arr + 1, arr + n + 1); int l = 0, r = n + 1; rep(i, 1, n) { if(!arr[i].ab) ans[++l] = arr[i].id; else ans[--r] = arr[i].id; }}int main(){ read(n); rep(i, 1, n) read(a[i]); rep(i, 1, n) read(b[i]); Johnson(); rep(i, 1, n) ti[i] = ti[i - 1] + a[ans[i]]; int sum = ti[1] + b[ans[1]]; rep(i, 2, n) sum = max(sum, ti[i]) + b[ans[i]]; cout << sum << endl; _for(i, 1, n) cout << ans[i] << " "; cout << ans[n] <