4.2.3 Job Processing 工序安排

4.2.3 Job Processing 工序安排

时间: 1ms        内存:64M

描述:

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

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

输入:

第一行 三个用空格分开的整数: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操作之前完成)。

示例输入:

5 2 3
1 1 3 1 4

示例输出:

3 5

提示:

参考答案(内存最优[820]):

#include <stdio.h>
#include <algorithm>
#include <functional>
#include <fstream>

#define min(a, b) (a>b?b:a)
#define max(a, b) (a>b?a:b)

using namespace std;

int d[3][55];
int leng[3][55];
int cost[3][1005];

int main()
{
	int n;
	while (scanf("%d %d %d", &n, &leng[1][0], &leng[2][0]) == 3)
	{
		int i, j, k;
		int et[3] = {0};
		for (i=1; i<=leng[1][0]; i++)
			scanf("%d", &leng[1][i]);
		for (i=1; i<=leng[2][0]; i++)
			scanf("%d", &leng[2][i]);
		for (i=1; i<3; i++)
		{
			for (j=1; j<=n; j++)
			{
				int min = 99999999;
				int s;
				for (k=1; k<=leng[i][0]; k++)
				{
					int t = d[i][k] + leng[i][k];
					if (min > t)
					{
						min = t;
						s = k;
					}
				}
				d[i][s] = min;
				cost[i][j] = min;
			}
		}
		sort(&cost[1][1], &cost[1][1] + n, less<int>());
		sort(&cost[2][1], &cost[2][1] + n, greater<int>());
		for (i=1; i<=n; i++)
		{
			et[1] = max(et[1], cost[1][i]);
			et[2] = max(et[2], (cost[1][i] + cost[2][i]));
		}
		printf("%d %d\n", et[1], et[2]);
	}
	return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
#include <algorithm>
#include <functional>
#include <fstream>

#define min(a, b) (a>b?b:a)
#define max(a, b) (a>b?a:b)

using namespace std;

int d[3][55];
int leng[3][55];
int cost[3][1005];

int main()
{
	int n;
	while (scanf("%d %d %d", &n, &leng[1][0], &leng[2][0]) == 3)
	{
		int i, j, k;
		int et[3] = {0};
		for (i=1; i<=leng[1][0]; i++)
			scanf("%d", &leng[1][i]);
		for (i=1; i<=leng[2][0]; i++)
			scanf("%d", &leng[2][i]);
		for (i=1; i<3; i++)
		{
			for (j=1; j<=n; j++)
			{
				int min = 99999999;
				int s;
				for (k=1; k<=leng[i][0]; k++)
				{
					int t = d[i][k] + leng[i][k];
					if (min > t)
					{
						min = t;
						s = k;
					}
				}
				d[i][s] = min;
				cost[i][j] = min;
			}
		}
		sort(&cost[1][1], &cost[1][1] + n, less<int>());
		sort(&cost[2][1], &cost[2][1] + n, greater<int>());
		for (i=1; i<=n; i++)
		{
			et[1] = max(et[1], cost[1][i]);
			et[2] = max(et[2], (cost[1][i] + cost[2][i]));
		}
		printf("%d %d\n", et[1], et[2]);
	}
	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注