P2751 [USACO4.2]工序安排Job Processing
- 18通过
- 78提交
- 题目提供者该用户不存在
- 标签
- 难度普及+/提高
提交 讨论 题解
最新讨论
- 暂时没有讨论
题目描述
一家工厂的流水线正在生产一种产品，这需要两种操作：操作A和操作B。每个操作只有一些机器能够完成。
Ioi96d1.gif
上图显示了按照下述方式工作的流水线的组织形式。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
分析：因为要使最后结束的时间尽量提前，如果一个产品在A操作和B操作上用时非常短，那么必然会有一个A操作和B操作用时很长，这样的话不是最优解，我们就要想办法把这些时间平均，很显然，A操作第i个完成的配B操作第n-i+1个完成的(A操作和B操作都是排好序的，具体为什么，请继续看)
那么怎么求第i个产品在A操作和B操作上的用时呢？每个机器加工一个产品的个数都是一定的，要使A操作和B操作有序，那么就要使第i个产品最先完成，开一个数组表示每个机器当前的时间，找当前时间+1个产品的加工时间最少的插入就行.
回到上面，A操作第i个完成的配B操作第n-i+1个完成可以看做第i个产品在A机器上和B机器上所分配的最平均的时间.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; int n, m1, m2,a[],b[],t[],t1[],t2[],cur,temp; int main()
{
scanf("%d%d%d", &n, &m1, &m2);
for (int i = ; i <= m1; i++)
scanf("%d", &a[i]);
for (int j = ; j <= m2; j++)
scanf("%d", &b[j]);
for (int i = ; i <= n; i++)
{
temp = ;
for (int j = ; j <= m1; j++)
if (t[j] + a[j] < temp)
{
temp = t[j] + a[j];
cur = j;
}
t[cur] = t1[i] = temp;
}
printf("%d ", temp);
memset(t, , sizeof(t));
for (int i = ; i <= n; i++)
{
temp = ;
for (int j = ; j <= m2; j++)
if (t[j] + b[j] < temp)
{
temp = t[j] + b[j];
cur = j;
}
t[cur] = t2[i] = temp;
}
int ans = ;
for (int i = ; i <= n; i++)
if (t1[i] + t2[n - i + ] > ans)
ans = t1[i] + t2[n - i + ];
printf("%d\n", ans);
//while (1); return ;
}