orz

Problem

有两个流水线，每条流水线有数台机器，每台机器加工一个产品需要一定时间，流水线 1 加工完成的产品才能被流水线 2 加工，每个机器加工的过程异步，共 $n$ 个产品，问流水线 1 和流水线 2 完工的最早时间。

Solution

考虑贪心。$f_i$ 为流水线 1 第 $i$ 个产品完工的最早时间。那么这个东西可以通过这样的贪心策略求出：将每个产品放到一个目前的结束时间最早的机器中。第一问的答案就是 $f_n$ 了。

考虑 $g_i$ 为流水线 2（独立于流水线 1 的）第 $i$ 个产品完工的最早时间。那么对于一个产品，我们可以令它为流水线 1 第 $i$ 个完工的，可以令它为流水线 2 第 $j$ 个完工的，那么它完工的最早时间就是 $f_i+g_j$。

问题被我们转化成了：给定两个长度相等的递增数列，在其中选出 $n$ 对数 $(f_i, g_j)$ 使得 $max(f_i+g_j)$ 最小。则每次选择 $f$ 中的最小值和 $g$ 中的最大值搭配即可，反证法可证。

Code

/*
ID: a1162731
TASK: job
LANG: C++11
*/

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+10;

int x[N], y[N], f[N], g[N], a[N], b[N];

int main() {
    #ifndef LOCAL
    freopen("job.in","r",stdin);
    freopen("job.out","w",stdout);
    #endif
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m1, m2;
    cin>>n>>m1>>m2;
    for(int i=0;i<m1;i++) cin>>x[i], a[i]=x[i];
    for(int j=0;j<m2;j++) cin>>y[j], b[j]=y[j];
    int p1, p2;
    for(int i=0;i<n;i++) {
        f[i]=g[i]=0x3f3f3f3f;
        for(int j=0;j<m1;j++) if(x[j]<f[i]) f[i]=x[j], p1=j;
        for(int j=0;j<m2;j++) if(y[j]<g[i]) g[i]=y[j], p2=j;
        x[p1]+=a[p1], y[p2]+=b[p2];
    }
    int ans=0;
    for(int i=0;i<n;i++) ans=max(ans, f[i]+g[n-i-1]);
    cout<<f[n-1]<<' '<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-usaco-job.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆