A factory is running a production line that requires two operations to be performed on each job: first operation "A" then operation "B". Only a certain number of machines are capable of performing each operation.
Figure 1 shows the organization of the production line that works as follows. A type "A" machine takes a job from the input container, performs operation "A" and puts the job into the intermediate container.
A type "B" machine takes a job from the intermediate container, performs operation "B" and puts the job into the output container. All machines can work in parallel and independently of each other, and the size of each container is unlimited. The machines
have different performance characteristics, a given machine requires a given processing time for its operation.
Give the earliest time operation "A" can be completed for all N jobs provided that the jobs are available at time 0. Compute the minimal amount of time that is necessary to perform both operations (successively,
of course) on all N jobs.
PROGRAM NAME: job
INPUT FORMAT
Line 1: |
Three space-separated integers:
- N, the number of jobs (1<=N<=1000).
- M1, the number of type "A" machines (1<=M1<=30)
- M2, the number of type "B" machines (1<=M2<=30)
|
Line 2..etc: |
M1 integers that are the job processing times of each type "A" machine (1..20) followed by M2 integers, the job processing times of each type "B" machine (1..20). |
SAMPLE INPUT (file job.in)
5 2 3
1 1 3 1 4
OUTPUT FORMAT
A single line containing two integers: the minimum time to perform all "A" tasks and the minimum time to perform all "B" tasks (which require "A" tasks, of course).
SAMPLE OUTPUT (file job.out)
3 5
关于求A的最短时间,最先想到的是DP,而总时间的最小值该怎么求一直没有好的思路,感觉这个问题和4.1的fence rail 有些相似,最后只好搜索加剪枝,前6个点能过,第7个点超时,后来听ZZY说这个可以用贪心,再上网看了些解题报告,终于豁然开朗。在此推荐一个解释得比较清晰的博客:http://magicalcode.blogbus.com/logs/37193487.html
下面是我的代码:
#include<cstdio>
#include<algorithm>
#define oo 1000000
using namespace std;
FILE *in,*out;
int n,a,b,ta[30],tb[30],cost[30],tableA[10001],tableB[10001];
void greedy(int *arr,int len,int *rec);
bool cmp(const int &a,const int & b);
int main()
{
in=fopen("job.in","r");
out=fopen("job.out","w");
fscanf(in,"%d%d%d",&n,&a,&b);
for(int i=0;i<a;i++) fscanf(in,"%d",&ta[i]);
for(int i=0;i<b;i++) fscanf(in,"%d",&tb[i]);
greedy(ta,a,tableA);
greedy(tb,b,tableB);
int max=0;
sort(tableA,tableA+n);
fprintf(out,"%d ",tableA[n-1]);
sort(tableB,tableB+n,cmp);
for(int i=0;i<n;i++) if(max<(tableA[i]+tableB[i])) max=tableA[i]+tableB[i];
fprintf(out,"%d\n",max);
fclose(in);
fclose(out);
return 0;
}
void greedy(int *arr,int len,int *rec)
{
for(int i=0;i<len;i++) cost[i]=0;
for(int i=0;i<n;i++)
{
int min=oo;
int index;
for(int j=0;j<len;j++)
{
if(min>cost[j]+arr[j])
{
min=cost[j]+arr[j];
index=j;
}
}
cost[index]=min;
rec[i]=min;
}
}
bool cmp(const int &a,const int & b)
{
return a>b;
}
分享到:
相关推荐
第二行到第 N+1 行: 每行有三个整数,Si, Ei, 和 Ci 第一个星期,农夫约翰随便地让 第一行 两个整数,N (0 ) 和 M
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
usaco历年测试数据
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
USACO题集及答案
某些USACO题目的答案,很详细,代码清晰结构良好,算法高效易于调试
usaco的总结和心得 包括了对题目的分了和总结 以及对题目的解法概括
USACO历年比赛测试数据:2003年 方便大家测试
USACO做题代码
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
内含USACO全部测试数据,绝对全
USACO全部译题 USACO Training Program Gateway
usaco traning的全部数据 才要3分
USACO1.1的源代码,新手入门可用 Only post for the new c++ students
USACO所有题目的题解 NOCOW整理版
USACO历年比赛测试数据:2006年方便大家测试
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
含2001~2017全部比赛赛题测试数据 2001~2007 数据√ 题面× 标程题解× 2008~2010 数据√ 题面√ 标程题解× 2011~2017 数据√ 题面√ 标程题解√ 其中除2008~2010外其他年份均按照年度、月度、金银铜白金组别整理...
数据结构机考所参考的USACO网站所有题目的解题思路,资源比较稀有!