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