题解 P1248 【加工生产调度】
agicy
·
·
题解
首先，声明一点
第一篇题解的思路完全正确，但缺乏证明
第一篇题解的思路：
by ljc20020730
n个作业要在由两台机器M1和M2组成的流水线上完成加工．每个作业i必须先在M1上然后在M2上加工，时间分别为ai和bi。
确定这n个作业的加工顺序，使得从第一个任务开始在M1上加工到最后一个任务在M2上加工完成的总时间尽量小。
直观上，最优调度一定让M1没有空闲，M2的空闲时间尽量少。
提供的算法:
①使用数组f1[j] 存放a[i]<b[i]的作业；
②使用数组f2[k] 存放a[i]>=b[i]的作业;
③对f1[j]根据a[j]进行升序排列;
④对f2[k]根据b[k]进行降序排列;
⑤遍历两个数组，依次求时间:取两个机器运行时间的较大值作为作业用时。
程序易于实现，时间O(nlogn)，关键在于正确性证明。
下面是我给出的证明
设S={J_1,J_2···J_n}，为待加工部件的作业排序，若A机器开始加工S中的部件时，B机器还在加工其他部件，t时刻后B机器可加工A机器加工过的部件。在这样的条件下，加工S中任务的最短时间T(S,t)={a_i+T(S-{J_i},b_i+max{t-a_i,0})}。
设最佳的方案中，现加工作业J_i，然后加工作业J_j，则
$=a_i+a_j+T(S-${$j_i,J_j$}$,b_j+max${$t-a_i,0$}$-a_j,0$}$)
=a_i+a_j+T(S-${$J-i,J_j$}$,T_{ij})
所以
T_{ij}=$ $\begin{cases}t+b_i+b_j-a_i-a_j(if(max(t,a_i,a_i+a_j-b_i)==t))\\b_i+b_j-a_j(if(max(t,a_i,a_i+a_j-b_i)==a_i))\\b_j(if(max(t,a_i,a_i+a_j-b_i)==a_j-b_i))\end{cases}
将工作顺序调换，则同理可得
又因为假设
>现加工作业$J_i$，然后加工作业$J_j$是最佳情况
所以
$max${$t,a_i,a_i+a_j-b_j$}$≤$ $max${$t,a_i,a_i+a_j-b_i$}
即
$min${$b_j,a_i$}$≤min${$b_i,a_j$}
所以按照上面的操作符合证明结果，可以得到最优解，证明完毕。
Q：那为什么这样做得到$24$分。
A：这道题出得不好，未开启$SPJ$，排序时不能使用不稳定的排序方法，如快速排序，所以用了```std::sort();```的人全都只有$24$分。
总的来说，这道题有毒，不推荐大家尝试。
[我的60分测评记录](https://www.luogu.org/record/show?rid=8040707)
$60$分，代码如下
```
#include<stdio.h>
struct Node{
int M,ID;
bool operator<=(Node a){
return this->M<=a.M;
}
Node operator=(Node a){
this->M=a.M;
this->ID=a.ID;
}
};
int n,A[1000],B[1000],ans[1000],index1,index2,time1,time2,i,j;
Node C[1000],temp;
/*
Memory=20,036 Byte=19.566,406,25 KB
*/
int min(int a,int b){
return a<b?a:b;
}
void swap(Node &a,Node &b){
temp=a,a=b,b=temp;
return;
}
int main(void){
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&A[i]);
for(i=0;i<n;i++)
scanf("%d",&B[i]),
C[i].M=min(A[i],B[i]),
C[i].ID=i;
//下面是超级稳定的排序算法，O(n^2)
for(i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(C[i].M>C[j].M)
swap(C[i],C[j]);
//排序结束
for(i=0,index1=0,index2=n-1;i<n;i++)
if(C[i].M==A[C[i].ID])
ans[index1++]=C[i].ID;
else
ans[index2--]=C[i].ID;
for(i=0;i<n;i++)
time1+=A[ans[i]],
time2=((time2<time1)?(time1):(time2)),
time2+=B[ans[i]];
printf("%d\n",time2);
for(i=0;i<n;i++)
printf("%d ",ans[i]+1);
return 0;
}
```