USACO - 1.2.1 - Milking Cows_JAVA_编程开发_程序员俱乐部

转载请注明出处

?

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

?

?? ? ? ? ?三个农民每天清晨5点起床，然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶，一直到1000秒。第二个农民在700秒开始，在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。

??????????PROGRAM NAME:milk2

??????????INPUT FORMAT:

??????????OUTPUT FORMAT:

?

??????????(file milk2.out)

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

二. ?题解

三. ?代码

?

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