- 浏览: 37632 次
- 性别:
- 来自: 北京
最新评论
-
andyshar:
请问如何在现有的hadoop环境中安装?
Hadoop集群监控系统Ambari安装 -
qingtangpaomian:
失败123 写道您好楼主: 我装好之后为啥老是最后一 ...
Hadoop集群监控系统Ambari安装 -
失败123:
您好楼主: 我装好之后为啥老是最后一步Cluster ...
Hadoop集群监控系统Ambari安装
转载请注明出处
摘要:模拟 ,先排序 ,区间相交
一. 题目翻译
1. 描述:
三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒。第二个农民在700秒开始,在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。
你的任务是编一个程序,读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表,计算以下两点(均以秒为单位):
a. 最长至少有一人在挤奶的时间段。
b. 最长的无人挤奶的时间段。(从有人挤奶开始算起)
2. 格式:
PROGRAM NAME:milk2
INPUT FORMAT:
(file milk2.in)
Line 1:
一个整数N。
Lines 2..N+1
每行两个小于1000000的非负整数,表示一个农民的开始时刻与结束时刻。
OUTPUT FORMAT:
(file milk2.out)
一行,两个整数,即题目所要求的两个答案。
SAMPLE INPUT:
SAMPLE OUTPUT:
二. 题解
1. 题意理解(将问题分析清楚,大致用什么思路):
这道题目可以直接模拟,但是在大数据量得情况下复杂度会比较高。
一种思路是,我们用一个数组记录所有奶农们开始挤奶的时间与结束挤奶的时间(注意开始时间与结束时间需要用一个标志位标记),然后对这个数组排序。后面的思路就类似于括号匹配了,在一段时间内有奶农挤奶就是说在这个时间段上至少有一对匹配的开始时间与结束时间。
2. 具体实现(具体实现过程中出现的问题):
具体实现是我们用如下变量记录一个时间段的相关特性:1. index该时间段起始位置。2.left记录挤奶开始时间的个数(类似于括号匹配中的左括号)。3.right记录挤奶结束时间的个数(类似于右括号)。
如果当前时间段left=right,则表示当前时间段有left个奶农正在挤奶。我们计算出当前时间段的维持时间与maxDuarance比较,记录当前时间段与上一个时间段之间的间隔与maxInterval比较。
上述操作做完后,开始计算下一个时间段(更新index,left,right变量)。
3. 启示:
这道题与有道的笔试题是类似的,可以一起记忆,积累这种求区间相交题目的思路。
三. 代码
package session_1_2_1; import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io.PrintWriter; import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; //特别注意有相同的开始、结束的点的问题。 //关注一下其他的算法 public class milk2 { public static void main(String[] args) { try { Scanner in = new Scanner(new BufferedReader(new FileReader("F:\\UCASO\\temp\\milk2.in"))); PrintWriter pw = new PrintWriter(new FileWriter("F:\\UCASO\\temp\\milk2.out")); int num = in.nextInt(); Block[] blocks = new Block[2*num]; for (int i=0;i<num;i++){ blocks[2*i] = new Block(in.nextInt(),0); blocks[2*i+1] = new Block(in.nextInt(),1); } Arrays.sort(blocks,new Compare()); int index = 0; int maxDuarance = 0; int maxInterval = 0; int left = 0; int right = 0; for (int i=0;i<blocks.length;i++){ if (blocks[i].type == 0){ left ++; } else { right ++; } if (left == right){ maxDuarance = blocks[i].point-blocks[index].point>maxDuarance?blocks[i].point-blocks[index].point:maxDuarance; if (index == 0){ maxInterval = 0; } else { maxInterval = blocks[index].point-blocks[index-1].point>maxInterval?blocks[index].point-blocks[index-1].point:maxInterval; } index = i+1; left = 0; right = 0; } } System.out.println(maxDuarance+" "+maxInterval); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } } } class Compare implements Comparator<Block>{ @Override public int compare(Block o1, Block o2) { if (o1.point > o2.point){ return 1; } else if (o1.point < o2.point){ return -1; } else { if (o1.type == o2.type){ return 0; } else if (o1.type < o2.type){ return -1; } else { return 1; } } } } class Block { int point; int type ; Block (int point , int type ){ this.point = point; this.type =type ; } }
发表评论
-
USACO - 3.2.2 - Stringsobits
2012-08-23 16:02 805原创文章转载请注明 ... -
USACO - 3.2.1 - Factorials
2012-08-23 16:01 697原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.6 - Stamps
2012-08-23 16:01 1034原创文章转载请注明 ... -
USACO - 3.1.5 - Contact
2012-08-23 16:01 906原创文章转载请注明出处 摘要:二叉树的应用 , ... -
USACO - 3.1.3 - Humble Numbers
2012-08-23 16:00 710原创文章转载请注明 ... -
USACO - 3.1.2 - Score Inflation
2012-08-22 10:05 902原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.1 - Agri-Net
2012-08-22 10:04 852原创文章转载请注明出处 摘要:Prim算法 , ... -
USACO - 2.4.5 - Fractions to Decimals
2012-08-22 10:04 958原创文章转载请注明出处 摘要:模拟 , 数论 ... -
USACO - 2.4.4 - Bessie Come Home
2012-08-22 10:04 902原创文章转载请注明出处 摘要:Dijkstra ... -
USACO - 2.4.2 - Overfencing
2012-08-22 10:03 998原创文章转载请注明 ... -
USACO - 2.4.1 - The Tamworth Two
2012-08-21 10:37 715原创文章转载请注明出处 摘要:模拟 ... -
USACO - 2.3.5 - Controlling Companies
2012-08-21 10:37 1299原创文章转载请注明出处 摘要:BFS , 模拟 ... -
USACO - 2.3.4 - Money Systems
2012-08-21 10:37 865原创文章转载请注明 ... -
USACO - 2.3.3 - Zero Sum
2012-08-21 10:36 741原创文章转载请注明出处 摘要:dfs , 枚举 ... -
USACO - 2.3.2 - Cow Pedigrees
2012-08-21 10:36 1007原创文章转载请注明 ... -
USACO - 2.3.1 - Longest Prefix
2012-08-20 20:31 1039原创文章转载请注明 ... -
USACO - 2.2.4 - Party Lamps
2012-08-20 20:30 1205原创文章转载请注明出处 摘要:枚举,三星 ... -
USACO - 2.2.3 - Runaround Numbers
2012-08-20 20:30 657原创文章转载请注明 ... -
USACO - 2.2.2 - Subset Sums
2012-08-20 20:30 692原创文章转载请注明出处 摘要:动态规划 ,0- ... -
USACO - 2.2.1 - Preface Numbering
2012-08-20 20:29 888原创文章转载请注明出处 摘要:模拟 , 数学分析 ...
相关推荐
USACO题目Milking Cows及代码解析
USACO题目,Greedy Gift Givers
此c++代码实现了USACO上Bessie Come Home的问题,并运用了弗洛伊德算法
此C++程序是实现了USACO网站上的Magic Squares的问题。
该题来自USACO,为最长串的查找,此处方法很笨,有更好方法
USACO chapter one.May hope it useful to someone
USACO chapter two.Useful for beginners.
usaco 上的题目barn1,beads,calfflac,可到那里查看具体题目
Notes-USACO-2021-弹簧
USACO-Cpp
C-Usaco-Work:Usaco在C中的工作
USACO-实践USACO 培训网站的工作实践代码! 100% 工作 - 大部分优化 - 混合语言
这是USACO2001-2007月赛全集。 usaco是美国中学生的官方竞赛网站。是美国著名在线题库,专门为信息学竞赛选手准备。推荐直接阅读英语原文,既准确可靠又可提高英语水平。做题方式模拟正式比赛,采用标准测评机、文件...
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
[USACO 1.2.1]挤牛奶答案 想要完整思路请关注+私信
USACO培训网站 我为章节解决方案。 每个文件的多行USACO标识信息注释 第1章全部的解决方案 第2章全部的解决方案
USACO-TurtleCamera 该存储库包含我对USACO问题的所有解决方案。 CSE 199工作区目录将是我用来帮助开发USACO课程的主要目录。
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
我的USACO题解和程序
Java中的USACO金问题 YYMM 姓名 文件夹 笔记 代码 1812 美食 1812 牛适应性 1812 团队合作