Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
这题java给的内存不够啊!到现在都没人AC过 附代码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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator