洛谷 P2751 [USACO4.2]工序安排Job Processing 题解【贪心】

作者: wjyyy 分类: 解题报告,贪心 发布时间: 2018-07-10 23:00

点击量:19

 

   类似排队接水?

 

题目描述

一家工厂的流水线正在生产一种产品,这需要两种操作:操作A和操作B。每个操作只有一些机器能够完成。

上图显示了按照下述方式工作的流水线的组织形式。A型机器从输入库接受工件,对其施加操作A,得到的中间产品存放在缓冲库。B型机器从缓冲库接受中间产品,对其施加操作B,得到的最终产品存放在输出库。所有的机器平行并且独立地工作,每个库的容量没有限制。每台机器的工作效率可能不同,一台机器完成一次操作需要一定的时间。

 

给出每台机器完成一次操作的时间,计算完成A操作的时间总和的最小值,和完成B操作的时间总和的最小值。

 

注:1、机器在一次操作中干掉一个工件; 2、时间总和的意思是最晚时间点

 

输入输出格式

输入格式:

第一行 三个用空格分开的整数:N,工件数量 (1<=N<=1000);M1,A型机器的数量 (1<=M1<=30);M2,B型机器的数量 (1<=M2<=30)。

 

第二行…等 M1个整数(表示A型机器完成一次操作的时间,1..20),接着是M2个整数(B型机器完成一次操作的时间,1..20)

 

输出格式:

只有一行。输出两个整数:完成所有A操作的时间总和的最小值,和完成所有B操作的时间总和的最小值(A操作必须在B操作之前完成)。

 

输入输出样例

输入样例#1:
5 2 3
1 1 3 1 4
输出样例#1:
3 5

说明

题目翻译来自NOCOW。

 

USACO Training Section 4.2

 

题解:

   第一问,类似排队接水,只不过贪心的条件变了。设si为队列i的原长,mi为队列i每接一次水耗费的时间。因为每个队伍的mi不同,所以我们要找si+mi最小的队列,排在它后面,更新si长度为si+mi。因为放置工件不分先后顺序,所以在队列里也是可以前后互换的,就如DP中的无后效性,第一问就做出来了。

 

   第二问,假设与第一问无关,我们认为当前时间点上,所有工件都可以使用,那么问题又演变成了同样的排队接水问题。因为同一工件的加工时间不能重叠,同一机器的加工时间也不能重叠,同时保证加工时间最长的工件时间最小(有点像二分?)。而前后加工的工件如果不重合,是可以任意匹配的,所以我们把第一个机器时间第i长的与第二个机器时间倒数第i长的配对,把它们当作一个工件。假设所有工件一起开始,一起结束,找到所有配对中和最大的当作开始时间与结束时间的间隔,就会使所有工件不自相重合。并且第一个机器最长的配了第二个机器最小的,根据名次推下去,总匹配到最优的工序。

 

   如图,在左边找到了最优匹配方案(保证了最长的最小),我们如果将它对齐,会得到右边的图,因为一定有至少一条位置不会改变,所以也证明了它是最长加工时间的工件。

 

   以后遇到这种进程题目最好往平移的方面去想,最后再想办法把它拼起来,虽然不一定所有的都符合,但是记住这个思路,就多一种方法。例如[HNOI2001]产品加工 题解

 

Code:

#include<cstdio>
#include<cstring>
int a[32],b[32];
int m1[32],m2[32];
int s1[1010],s2[1010];
int main()
{
    int n,ans=0;
    scanf("%d%d%d",&n,&m1[0],&m2[0]);
    m1[31]=0x3fffffff;
    m2[31]=0x3fffffff;
    for(int i=1;i<=m1[0];i++)
        scanf("%d",&m1[i]);
    for(int i=1;i<=m2[0];i++)
        scanf("%d",&m2[i]);
    for(int i=1;i<=n;i++)//第一遍贪心
    {
        int tmp=31;
        for(int j=1;j<=m1[0];j++)
            if(a[j]+m1[j]<a[tmp]+m1[tmp])
                tmp=j;
        a[tmp]+=m1[tmp];
        s1[i]=a[tmp];
        ans=ans>s1[i]?ans:s1[i];
    }
    printf("%d ",ans);//第一问
    for(int i=1;i<=n;i++)//第二遍贪心
    {
        int tmp=31;
        for(int j=1;j<=m2[0];j++)
            if(b[j]+m2[j]<b[tmp]+m2[tmp])
                tmp=j;
        b[tmp]+=m2[tmp];
        s2[i]=b[tmp];
    }
    ans=0;
    for(int i=1;i<=n;i++)//拼接两问答案
        ans=ans>s1[i]+s2[n-i+1]?ans:s1[i]+s2[n-i+1];
    printf("%d\n",ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */