Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这题java给的内存不够啊!到现在都没人AC过 附代码

Posted by WutongDeath at 2008-01-22 01:22:55 on Problem 1763
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

class MyComp_x implements Comparator {
	public int compare(Object o1, Object o2) {
		int[] p1 = (int[])o1;
		int[] p2 = (int[])o2;
		if(p1[0] < p2[0])
			return -1;
		if(p1[0] > p2[0])
			return 1;
		if(p1[1] < p2[1])
			return -1;
		if(p1[1] > p2[1])
			return 1;
		return 0;
	}
}
class MyComp_y implements Comparator {
	public int compare(Object o1, Object o2) {
		int[] p1 = (int[])o1;
		int[] p2 = (int[])o2;
		if(p1[1] < p2[1])
			return -1;
		if(p1[1] > p2[1])
			return 1;
		if(p1[0] < p2[0])
			return -1;
		if(p1[0] > p2[0])
			return 1;
		return 0;
	}
}
public class Main {
	static int n, x, y, l = 250000, b, e;
	static char d;
	static char[] arr;
	static int[][] route;
	private static void input() throws NumberFormatException, IOException {
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(stdin.readLine());
		arr = stdin.readLine().toCharArray();
		x = 0;
		y = 0;
		route = new int[n+1][3];
		for(int i = 0; i <= n; ++i) {
			route[i][0] = x;
			route[i][1] = y;
			route[i][2] = i;
			if(i != n) {
				if(arr[i] == 'W') {
					--x;
				} else if(arr[i] == 'E') {
					++x;
				} else if(arr[i] == 'S') {
					--y;
				} else if(arr[i] == 'N') {
					++y;
				}
			}
		}
	}
	private static void solve() {
		Arrays.sort(route, new MyComp_x());
		int tmp, min, max;
		for(int i = 1; i < n; ++i) {
			if(route[i-1][0] == route[i][0]) {
				tmp = route[i][1] - route[i-1][1];
				if(route[i-1][2] < route[i][2]) {
					min = route[i-1][2];
					max = route[i][2];
				} else {
					min = route[i][2];
					max = route[i-1][2];
				}
				if(
						(Math.abs(route[i-1][2] - route[i][2]) != tmp) &&
						(tmp < l ||
						(tmp == l && (min < b || (min == b && max > e))))
				) {
					l = tmp;
					b = min;
					e = max;
					if(route[i-1][2] < route[i][2]) {
						if(route[i-1][1] < route[i][1])
							d = 'N';
						else
							d = 'S';
					} else {
						if(route[i-1][1] < route[i][1])
							d = 'S';
						else
							d = 'N';
					}
				}
			}
		}
		Arrays.sort(route, new MyComp_y());
		for(int i = 1; i < n; ++i) {
			if(route[i-1][1] == route[i][1]) {
				tmp = route[i][0] - route[i-1][0];
				if(route[i-1][2] < route[i][2]) {
					min = route[i-1][2];
					max = route[i][2];
				} else {
					min = route[i][2];
					max = route[i-1][2];
				}
				if(
						(Math.abs(route[i-1][2] - route[i][2]) != tmp) &&
						(tmp < l ||
						(tmp == l && (min < b || (min == b && max > e))))
				) {
					l = tmp;
					b = min;
					e = max;
					if(route[i-1][2] < route[i][2]) {
						if(route[i-1][0] < route[i][0])
							d = 'E';
						else
							d = 'W';
					} else {
						if(route[i-1][0] < route[i][0])
							d = 'W';
						else
							d = 'E';
					}
				}
			}
		}
	}
	public static void main(String args[]) throws NumberFormatException, IOException {
		input();
		solve();
		System.out.println(l + " " + b + " " + e + " " + d);
	}

}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator