题解 P2751 【[USACO4.2]工序安排Job Processing】

· · 题解

虽然代码和诸位大佬相去不远，但我的思路似乎有所不同。

假定所有的A机器同时开始，所有的B机器同时结束。

为什么可以这样想？因为结束时间不一样某种安排方案，我们可以找出那台最晚结束的B,然后把比它早结束的推迟一点，这样既不影响全局结束时间，又好理解。

首先考虑每一个物品，令f[i]表示第i个开始加工的物品处理完毕的最短时间，g[i]表示开始加工倒数第i个完成的物品距离“设定结束时间”的最短时间（其实和f[i]是一个意思）。

然后，完成一个成品就需要f[i]+g[j]的时间（i,j<=n）

最后贪心的想，先完成的物品要离结束尽量远，后完成的物品要离结束尽量近。因此不如直接把离结束最近的和最晚开始的凑成一对，离结束第二近的和第二晚开始的凑成一对......这样每一个物品都有了着落，耗时最长的物品就是全局时间。

但，考虑一下，这为什么是对的？我的意思是，f[i]+g[j]怎么就一定能表示一种可行解呢？难道不会出现，后完场的反而先做的情况吗？

实际上，假如i,j真的任意取，的确会这样。但在上述的“长配短”匹配当中，已经保证了 先被A加工完了的物品 ，一定不会排在 后被A加工完的物品 之后去被B加工。

思路清奇，但代码却十分简洁。

#include<iostream>
#include<cstdio>
#define N 100
#define M 2020
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,A,B,a[N],b[N],x[N],y[N],f[M],g[M],p,q,ans;
int main(){
    scanf("%d%d%d",&n,&A,&B);
    FOR(i,1,A) scanf("%d",&a[i]),x[i]=a[i];
    FOR(i,1,B) scanf("%d",&b[i]),y[i]=b[i];
    FOR(i,1,n){
        f[i]=g[i]=1000010000;
        FOR(j,1,A) if(x[j]<f[i]) p=j,f[i]=x[j];
        FOR(j,1,B) if(y[j]<g[i]) q=j,g[i]=y[j];
        x[p]+=a[p],y[q]+=b[q]; 
    }FOR(i,1,n) ans=max(ans,f[i]+g[n-i+1]);
    printf("%d %d",f[n],ans);
}