首页 > 专题系列 > Java解POJ > POJ 1661 Help Jimmy [解题报告] Java
2013
11-10

POJ 1661 Help Jimmy [解题报告] Java

Help Jimmy

问题描述 :

“Help Jimmy” 是在下图所示的场景上完成的游戏。



场景中包括多个长度和高度各不相同的平台。地面是最低的平台,高度为零,长度无限。

Jimmy老鼠在时刻0从高于所有平台的某处开始下落,它的下落速度始终为1米/秒。当Jimmy落到某个平台上时,游戏者选择让它向左还是向右跑,它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时,开始继续下落。Jimmy每次下落的高度不能超过MAX米,不然就会摔死,游戏也会结束。

设计一个程序,计算Jimmy到底地面时可能的最早时间。

输入:

第一行是测试数据的组数t(0 <= t <= 20)。每组测试数据的第一行是四个整数N,X,Y,MAX,用空格分隔。N是平台的数目(不包括地面),X和Y是Jimmy开始下落的位置的横竖坐标,MAX是一次下落的最大高度。接下来的N行每行描述一个平台,包括三个整数,X1[i],X2[i]和H[i]。H[i]表示平台的高度,X1[i]和X2[i]表示平台左右端点的横坐标。1 <= N <= 1000,-20000 <= X, X1[i], X2[i] <= 20000,0 < H[i] < Y <= 20000(i = 1..N)。所有坐标的单位都是米。

Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的边缘,被视为落在平台上。所有的平台均不重叠或相连。测试数据保证问题一定有解。

输出:

对输入的每组测试数据,输出一个整数,Jimmy到底地面时可能的最早时间。

样例输入:

1
3 8 17 20
0 10 8
0 10 13
4 14 3

样例输出:

23

解题代码:

import java.util.Arrays;
import java.util.Scanner;

/**
 * POJ1661
 * @author Bruce
 *
 */

class Board implements Comparable{
	int lx;
	int rx;
	int h;
	public Board(int x,int y,int h){
		this.lx = x;
		this.rx = y;
		this.h = h;
	}
	public int compareTo(Board b) {		
		return b.h - this.h;//���楂�害���
	}	
}

public class Main{
	static final int MAX_VALUE = 100000000;
	static int[] leftMin;
	static int[] rightMin;	
	static Board[] boards;
	static int max;
	static int N;
	public static int min(int i,boolean isLeft){
		int x;
		int y = boards[i].h;
		if(isLeft)
			x = boards[i].lx;
		else
			x = boards[i].rx;
		int j;
		for(j=i+1;j<=N;j++){
			if(boards[j].lx <= x && boards[j].rx >= x)//涓�����瀛�
				break;
		}
		if(j > N){//涓��娌℃��垮�
			if(y > max)
				return MAX_VALUE;
			else 
				return y;
		}else{//����规��垮���reak浜�
			if(y - boards[j].h > max)
				return MAX_VALUE;
			else{
				if(leftMin[j] == -1)
					leftMin[j] = min(j,true);
				if(rightMin[j] == -1)
					rightMin[j] = min(j,false);
	return (y - boards[j].h) + Math.min(leftMin[j]+x-boards[j].lx, rightMin[j]+boards[j].rx-x);
			}
		}
			
	}
	
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		for(int i=0;i< T;i++){
			N = in.nextInt();
			int x = in.nextInt();
			int y = in.nextInt();
			max = in.nextInt();
			leftMin = new int[N+1];
			rightMin = new int[N+1];	
			Arrays.fill(leftMin, -1);
			Arrays.fill(rightMin, -1);
			
			boards = new Board[N+1];
			boards[0] = new Board(x,x,y);
			for(int j=1;j<=N;j++){
				boards[j] = new Board(in.nextInt(),in.nextInt(),in.nextInt());
			}
			Arrays.sort(boards);
			System.out.println(min(0,true));			
		}
	}
}

  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks