A factory is running a production line that requires two operations to be performed on each job: first operation "A" then operation "B". Only a certain number of machines are capable of performing each operation.
Give the earliest time operation "A" can be completed for all N jobs provided that the jobs are available at time 0. Compute the minimal amount of time that is necessary to perform both operations (successively, of course) on all N jobs.
| Line 1: | Three space-separated integers:
|
| Line 2..etc: | M1 integers that are the job processing times of each type "A" machine (1..20) followed by M2 integers, the job processing times of each type "B" machine (1..20). |
5 2 3 1 1 3 1 4
3 5
开始还很怕这种贪心的题目，感觉需要很多数学的证明。今天研究了一下，其实也并不是很难。
第一问很好解决。我们枚举每台机子的状态，寻找当前第i个产品放在哪里更快，并同时更新机器和商品的时间。等所有商品都枚举好后，选一个时间最大的即可。（当然是最后一个处理的商品）
后来的B机器也可以同上述方法过。但是我们会发现，B机器是直接和A机器相关的，于是我们不能光把B机器处理产品的最大时间输出。那么我们贪心地想一想：在A机器处理好后的产品中，速度快的一些我放在B机器中处理慢的地方。这样才能使时间更均衡。因此第二问的答案就是max(time1[i]+time2[n-i+1])（其中time1和time2分别是第i快的产品在A,B机器里操作的时间）
代码：
/*
PROG:job
ID:juan1973
LANG:C++
*/
#include<stdio.h>
using namespace std;
const int maxn1=1001;const int maxn2=31;const int INF=2000000000;
int na,nb,n,i,j,min,ans,k;
int time1[maxn1],time2[maxn1],timea[maxn2],timeb[maxn2],a[maxn2],b[maxn2];
int main()
{
freopen("job.in","r",stdin);
freopen("job.out","w",stdout);
scanf("%ld%ld%ld",&n,&na,&nb);
for (i=1;i<=na;i++) scanf("%ld",&a[i]);
for (i=1;i<=nb;i++) scanf("%ld",&b[i]);
for (i=1;i<=n;i++)
{
min=INF;
for (j=1;j<=na;j++)
if (timea[j]+a[j]<min) {min=timea[j]+a[j];k=j;}
timea[k]=time1[i]=min;
}
printf("%ld ",min);
for (i=1;i<=n;i++)
{
min=INF;
for (j=1;j<=nb;j++)
if (timeb[j]+b[j]<min) {min=timeb[j]+b[j];k=j;}
timeb[k]=time2[i]=min;
}
ans=0;
for (i=1;i<=n;i++)
if (time1[i]+time2[n-i+1]>ans) ans=time1[i]+time2[n-i+1];
printf("%ld\n",ans);
//scanf("%ld",&n,&na,&nb);
return 0;
}usaco training 4.2.3 Job Processing 题解,布布扣,bubuko.com
usaco training 4.2.3 Job Processing 题解
原文：http://blog.csdn.net/jiangshibiao/article/details/20029695