USACO Training 4.2.3 Job Processing 工序安排 题解与分析

2024-06-07 07:18

本文主要是介绍USACO Training 4.2.3 Job Processing 工序安排 题解与分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Job Processing 工序安排

IOI'96


描述

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

Ioi96d1.gif

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

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

格式

PROGRAM NAME: job

INPUT FORMAT:

(file job.in)

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

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

OUTPUT FORMAT:

(file job.out)

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

SAMPLE INPUT

5 2 3
1 1 3 1 4

SAMPLE OUTPUT

3 5
【分析】:
    这道题用二分答案+贪心.
    首先对于A工序的总耗时二分一个答案x,然后验证这个时间是否合不合理:既不多,又不少.那么在这一段时间内可作出的工件数为∑x/time[i],1≤i≤M1,对该值进行判断即可.比较难想的是B工序的总耗时,首先算出完成一个工件的A工序后的时间点time1,如样例中A机器1 1,那么在时间ans1=3内这两台机器完成一个工件的时间分别为1,1,2,2,3,3,即表示:1时间点出1个工件<由A1机器制造>,1时间点出1个工件<由A2机器制造>,2时间点出1个工件<由A1机器制造>,2时间点出1个工件<由A2机器制造>,3时间点出1个工件<由A1机器制造>,3时间点出1个工件<由A2机器制造>.                              
    然后开始B工序的二分答案,如第一问二分方法,我们需检查二分出的数x是否满足条件.相应的,我们处理出所有完成一个工件的B工序后的时间点time2[i],那么x-time2[i]就是对于当前时间而言最晚开始B工序的时间点.类似的,我们将time2排序,筛出N个最小的time2,这样使得整体开始B工序的时间尽可能晚<若这里改为筛出N个最大的,那么这个二分永远找不出解,仔细想想>.
    最后判断是否对应的每个time1都小于等于time2,若不是就说明这种方案不行,应当继续二分
 
【代码】:
/*
ID:csyzcyj1
PROG:job
LANG:C++
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define MAXM 31
#define MAX 20001
#define IMAX 2147483647
int N,M1,M2,ans1=IMAX,ans2=IMAX,min1=IMAX,min2=IMAX,pos1[MAX],pos2[MAX],tot=0;
int a[MAXM],b[MAXM];
bool cmp(int x,int y){return x>y;}
bool check1(int x)
{
int now=0;
for(int i=1;i<=M1;i++)
now+=x/a[i];
if(now>=N)   return true;
else return false;
}
bool check2(int x)
{
int sum=0;
memset(pos2,0,sizeof(pos2));
for(int i=1;i<=M2;i++)
for(int j=1;j<=x/b[i];j++)
if(x-j*b[i]>0)   
pos2[++sum]=j*b[i];//算出完成一个工件的B工序后的时间点
if(sum<N)   return false;
sort(pos2+1,pos2+1+sum);
for(int i=1;i<=N;i++)
if(pos1[i]>x-pos2[i])//x-pos2[i]表示最晚开始B工序的时间 
return false;
return true;         
}
void work()
{
int left=1,right=min1*N;
while(left<=right)//二分完成A操作的总耗时 
{
int middle=(left+right)/2;
if(check1(middle))
right=middle-1;
else  left=middle+1;
}
ans1=left;
for(int i=1;i<=M1;i++)
for(int j=1;j<=ans1/a[i];j++)
pos1[++tot]=j*a[i];//算出完成一个工件的A工序后的时间点
sort(pos1+1,pos1+1+tot,cmp);
for(int i=1;i<=N;i++)
pos1[i]=pos1[i+tot-N];//筛出最小的N个时间 
left=ans1,right=ans1+min2*N;//二分完成B操作的总耗时 
while(left<=right)
{
int middle=(left+right)/2;
if(check2(middle))
right=middle-1;
else  left=middle+1;
}
ans2=left;
}
int main()
{
freopen("job.in","r",stdin);
freopen("job.out","w",stdout); 
scanf("%d%d%d",&N,&M1,&M2);
for(int i=1;i<=M1;i++)
{
scanf("%d",&a[i]);
min1=min(min1,a[i]);
}
for(int i=1;i<=M2;i++)
{
scanf("%d",&b[i]);
min2=min(min2,b[i]);
}
work();
printf("%d %d\n",ans1,ans2);
//system("pause");
return 0;
}
【评测信息】:
      Compiling...
      Compile: OK
      Executing...
      Test 1: TEST OK [0.000 secs, 3536 KB]
      Test 2: TEST OK [0.000 secs, 3536 KB]
      Test 3: TEST OK [0.000 secs, 3536 KB]
      Test 4: TEST OK [0.000 secs, 3536 KB]
      Test 5: TEST OK [0.000 secs, 3536 KB]
      Test 6: TEST OK [0.000 secs, 3536 KB]
      Test 7: TEST OK [0.000 secs, 3536 KB]
      Test 8: TEST OK [0.000 secs, 3536 KB] 
      Test 9: TEST OK [0.000 secs, 3536 KB]
      Test 10: TEST OK [0.011 secs, 3536 KB]
      Test 11: TEST OK [0.011 secs, 3536 KB]
      Test 12: TEST OK [0.011 secs, 3536 KB]
      All tests OK.
 

转载注明出处:http://blog.csdn.net/u011400953

这篇关于USACO Training 4.2.3 Job Processing 工序安排 题解与分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1038501

相关文章

SpringBoot中六种批量更新Mysql的方式效率对比分析

《SpringBoot中六种批量更新Mysql的方式效率对比分析》文章比较了MySQL大数据量批量更新的多种方法,指出REPLACEINTO和ONDUPLICATEKEY效率最高但存在数据风险,MyB... 目录效率比较测试结构数据库初始化测试数据批量修改方案第一种 for第二种 case when第三种

解决1093 - You can‘t specify target table报错问题及原因分析

《解决1093-Youcan‘tspecifytargettable报错问题及原因分析》MySQL1093错误因UPDATE/DELETE语句的FROM子句直接引用目标表或嵌套子查询导致,... 目录报js错原因分析具体原因解决办法方法一:使用临时表方法二:使用JOIN方法三:使用EXISTS示例总结报错原

MySQL中的LENGTH()函数用法详解与实例分析

《MySQL中的LENGTH()函数用法详解与实例分析》MySQLLENGTH()函数用于计算字符串的字节长度,区别于CHAR_LENGTH()的字符长度,适用于多字节字符集(如UTF-8)的数据验证... 目录1. LENGTH()函数的基本语法2. LENGTH()函数的返回值2.1 示例1:计算字符串

Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

《Androidkotlin中Channel和Flow的区别和选择使用场景分析》Kotlin协程中,Flow是冷数据流,按需触发,适合响应式数据处理;Channel是热数据流,持续发送,支持... 目录一、基本概念界定FlowChannel二、核心特性对比数据生产触发条件生产与消费的关系背压处理机制生命周期

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

python中Hash使用场景分析

《python中Hash使用场景分析》Python的hash()函数用于获取对象哈希值,常用于字典和集合,不可变类型可哈希,可变类型不可,常见算法包括除法、乘法、平方取中和随机数哈希,各有优缺点,需根... 目录python中的 Hash除法哈希算法乘法哈希算法平方取中法随机数哈希算法小结在Python中,

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重

关于MyISAM和InnoDB对比分析

《关于MyISAM和InnoDB对比分析》:本文主要介绍关于MyISAM和InnoDB对比分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录开篇:从交通规则看存储引擎选择理解存储引擎的基本概念技术原理对比1. 事务支持:ACID的守护者2. 锁机制:并发控制的艺