USACO Job Processing

可以看出，这道题是一个任务调度问题，对于A任务，很容易想到用贪心算法解决，即针对每个任务，选择完成时间最早的机器处理。那么，最后一个任务的结束时间就是完成所有A任务的最短时间。

然而，B任务，情况就不同了。B任务必须在有中间产物时才可以开始，因此，必须在第一个A任务结束后才可以开始。容易知道，当A全部完成后，B还需要花费时间加工，如果可以把这段时间缩短，就可以缩短总体时间。（读者也可以从“对称性”的角度分析）

于是，我们先用A的方法，计算在中间产物充足时完成每个B任务的时间。然后把这个时间逆序，把其中每一项和完成A任务的时间相加得到一个新的数组，这个数组的最大值就是完成所有工序的最短时间。

上面一段话写得有点乱。上面说到的方法其实是Johnson's Algorithm，wikipedia和这个页面上有更详细的介绍。

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <limits.h>
04 #define MAX_MACHINE 33
05 #define MAX_TIME 21
06
07 int na,nb,job;
08 int ta[MAX_MACHINE],tb[MAX_MACHINE];
09 long finish[2][1001];
10
11 int cmp(const void *a,const void *b)
12 {
13     return (*(int *)a - *(int *)b);
14 }
15
16 void init()
17 {
18     int i;
19     scanf("%d %d %d\n",&job,&na,&nb);
20     for(i = 0;i < na;i ++)
21         scanf("%d",&ta[i]);
22     for(i = 0;i < nb;i ++)
23         scanf("%d",&tb[i]);
24     qsort(ta,na,sizeof(int),cmp);
25     qsort(tb,nb,sizeof(int),cmp);
26 }
27
28 void solve_a()
29 {
30     int busy_until[MAX_MACHINE] = {};
31     int i,j;
32     int min,assignto;
33     for(i = 1;i <= job;i ++)
34     {
35         min = INT_MAX;
36         for(j = 0;j < na;j ++)
37         {
38             if(ta[j] + busy_until[j] < min)
39             {
40                 min = ta[j] + busy_until[j];
41                 assignto = j;
42             }
43         }
44         busy_until[assignto] = min;
45         finish[0][i] = min;
46         //printf("%d %ld\n",assignto,finish[0][i]);
47     }
48     printf("%ld ",finish[0][job]);
49 }
50
51 void solve_b()
52 {
53     int busy_until[MAX_MACHINE] = {};
54     int i,j;
55     int min,assignto;
56     for(i = 1;i <= job;i ++)
57     {
58         min = INT_MAX;
59         for(j = 0;j < nb;j ++)
60         {
61             if(tb[j] + busy_until[j] < min)
62             {
63                 min = tb[j] + busy_until[j];
64                 assignto = j;
65             }
66         }
67         busy_until[assignto] = min;
68         finish[1][i] = min;
69         //printf("%d %ld\n",assignto,finish[0][i]);
70     }
71     //printf("%ld ",finish[1][job]);
72 }
73
74 void combine()   //Johnson's Algorithm
75 {
76     int i;
77     long max = 0;
78     for(i = 1;i <= job;i ++)
79     {
80         if(finish[0][i] + finish[1][job - i + 1] > max)
81             max = finish[0][i] + finish[1][job - i + 1];
82     }
83     printf("%ld\n",max);
84 }
85
86 int main()
87 {
88     freopen("job.in","r",stdin);
89     freopen("job.out","w",stdout);
90     init();
91     solve_a();
92     solve_b();
93     combine();
94     return 0;
95 }