[USACO4.2] Job Processing [贪心]

ajcxsu
ajcxsu 2018年09月06日
  • 79 次阅读

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://acxblog.site/archives/sol-usaco-job.html
本文采用 CC BY-NC-SA 3.0 协议进行许可