题目理解

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

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

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

最后贪心的想，先完成的物品要离结束尽量远，后完成的物品要离结束尽量近。

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

算法1

(贪心) $O(n^2)$

C 代码

#include<stdio.h>
#define N 100
#define M 2020
#define INF 1e7
#define FOR(i,a,b) for(int i=a;i<=b;i++)
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]=INF;
        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=(ans>(f[i]+g[n-i+1]))?ans:(f[i]+g[n-i+1]);
    printf("%d %d",f[n],ans);
}