USACO 4.2.3 Job processing
对于第一问,比较容易想到.直接贪心就可以了,也就是每次都只处理一个任务,每次取当前结束时间最靠前的一个,这样的话,就可以保证总的结束时间一定是最早的.比如说5 2 3 1 1 3 1 4的话,那么一共会循环5次[也就是5个任务],第一次选第一台机器,因为它的结束时间是1,然后它的结束时间就会变成2[这里是指如果这个任务让这台机器来完成,那么完成之后的结束时间],第二次就会选第2台机器,因为第二台机器的结束时间还是1,依次类推,完成A任务的时间就会是1 1 2 2 3也就是一共需要3个单位的时间这是第一问的答案.那么第二问的答案就比这个要稍微难想一点,不过我们知道A B两项任务是没关系的,也就是进水不犯河水,各干各的.而且对于完成每个任务的每种机器也是各干各的,互不干扰.还有一点就是我们可以想象如果把完成A任务的和完成B任务的所需时间一个按从小到大排序,一个从大到小排序,然后对应的相加,也就是说完成A任务最早的放到B那就让它最晚完成,这样总的结束时间就会早一点.但是这里有个问题就是这样可以吗,因为B任务的开始是以A任务的结束为开始的,如果B任务那样一搞,但是A那某个还没完成咋办呢?这样我们来看看一个简单的分析,就那上面的例子来说,那么排序之后会是这样的
1 1 2 2 3
4 3 3 2 1[单独完成B任务所需的时间]这里还得说一点,就是这个时间是可以”换”的,也就是不一定要特定的任务在特定的机器上完成,反正就是里面的2和3 或者3和4之类的不是指的某个任务在第几个单位时间内完成,而是说最好的安排是有任务在第1个单位完成,有任务在第4个单位完成,这就OK了.
那么我们的第二问就是这样排列之后上下两个相加,然后取这些和的最大值.这里是5.但是就会有这样的疑问,也就是说下面那一排是首先不管A的,那么又没有可能是某个时候和下面对应的那个上面的任务还没问成呢?这样不是就不对了么?这里我们可以这样考虑,因为对于B中不同的机器之间是不存在这样的问题的,只有对于同一类机器,可是说同一台机器才会有这样的问题,因为不同机器是互不干扰的,那么我们单独考虑一台机器[B机器]
如果我们有如下的情况
1 3 6
6 4 2[这里是说明这台机器完成一件任务需要2分钟]
那么我们得到的结果应该是8[=2+6],那么第1分钟的时候第一件A任务完成了,现在我们可以让B的机器去做它,到了第3分钟刚好完成了,那么我们让它继续做第二件A任务,到了第5分钟的时候完成了,可是现在没有A任务给它,好的,这样更好,因为这样不会有我们认为的那种”忙不过来的”感觉.最终第6分钟来任务了,在第8分钟结束.
好了看看下面的一组数据
1 4 6
9 6 3
这里的数据是第1分钟B机器接到任务,然后第4分钟完成了,然后刚好接到第二个任务,继续做,到了第6分钟的时候,还没做完,怎么办?继续做原来的任务,这样就在第7分钟开始做等在那得第三个任务,可是这是不是一个巧合呢?下面就是见证奇迹的时候- -.其实这不是什么巧合,而是事实.你可以这样想,反正B任务得工作9个单位时间,这两个例子里面是不是都工作了9个单位时间呢?对啊,没错啊.可是还是有点糊涂,那么你可以把第一行的后一个减前一个得到一个差,这样就会得到另外一个数列,如下
3 2
这里要干嘛呢?你可以这样想,如果要是出现前面那种情况,那么后面的和会比较大[8比前面的大,这个原因就是上面的数列决定的]如果要是第二个例子的话,那么后面的结果不会比前面的大,这样只需要知道放在这台机器上工作的A任务的第一个任务的完成时间然后再加上一个几个任务*每个任务的时间久OK了.这样每台机器的搞清楚了,因为不同机器互不干扰,所以这样就是最佳答案了.
代码如下:
ID:qcx97811
LANG:C
TASK:job
/
#include
#include
#include
typedef struct
{
int end
int cost
}Node
Node aMachine[36],bMachine[36];
int N,A,B;
int aEnd[1006],bEnd[1006];
int total
int cmp(const void a,const void b)
{
Node c = (Node )a
Node d = (Node )b;
if(c->end == d->end)
return 0
if(c->end > d->end)
return 1
return -1
}
void work()
{
int tn,k,i
tn = N;
memset(aEnd,0,sizeof(aEnd));
i = 0
while(tn)
{//每次减少一个任务
qsort(aMachine,A,sizeof(aMachine[0]),cmp);//对结束时间排序
tn–
aEnd[i] = aMachine[0].end
aMachine[0].end += aMachine[0].cost//更改当前的结束时间
i++
}
#if 0
for(i = 0;i < N;i++)
printf(“%d\n”,aEnd[i]);
#endif
printf(“%d”,aEnd[N-1]);//这个是A Machine工作完所需的时间
tn = N;
i = 0
while(tn)
{
qsort(bMachine,B,sizeof(bMachine[0]),cmp);
tn–
bEnd[i] = bMachine[0].end
bMachine[0].end += bMachine[0].cost
i++
}
#if 0
printf(“\n”);
for(i = 0;i < N;i++)
printf(“####%d####\n”,bEnd[i]);
#endif
tn = aEnd[0]+bEnd[N-1];
for(i = 0i < N;i++)
{
if(aEnd[i] + bEnd[N-1-i] > tn)
tn = aEnd[i] + bEnd[N-1-i];
}
printf(“ %d\n“,tn);
}
void input(Node in[],int num)
{
int i
for(i = 0i < num;i++)
{
scanf(“%d”,in[i].cost);
in[i].end = in[i].cost
}
}
int main(void)
{
freopen(“job.in”,“r”,stdin);
freopen(“job.out”,“w”,stdout);
int i
scanf(“%d%d%d”,N,&A,&B);
input(aMachine,A);
input(bMachine,B);
work();
return 0
}
