USACO - 1.2.1 - Milking Cows

转载请注明出处

 

摘要：模拟 ，先排序 ，区间相交

 

一. 题目翻译

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)

          一行，两个整数，即题目所要求的两个答案。

3. SAMPLE：

          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 ;
	}
}