之前其实我用了非离散化的方式过了,最近学习离散化,想问问,这题能不能离散化,我这边是直接 MLE 了。
// 这题能离散化吗?我 MLE 了
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
final int MAX = 10005;
int[] x = new int[MAX];
int[] y = new int[MAX];
int[] rank = new int[MAX]; // 离散化后的数据
int[][] board = new int[MAX][MAX];
ArrayList<Integer> list = new ArrayList<>();
int n = sc.nextInt(), cnt = 0, m = 0;
for(int i = 0; i < n; i++) {
int a = sc.nextInt(), b = sc.nextInt(), g = sc.nextInt(), k = sc.nextInt();
x[cnt] = a;
y[cnt] = b;
list.add(x[cnt]);
list.add(y[cnt]);
cnt++;
x[cnt] = a + g;
y[cnt] = b + k;
list.add(x[cnt]);
list.add(y[cnt]);
cnt++;
}
x[cnt] = sc.nextInt();
y[cnt] = sc.nextInt();
list.add(x[cnt]);
list.add(y[cnt]);
cnt++;
// 排序
Collections.sort(list);
int size = list.size();
// 进行 离散化 + 去重
for(int i = 0; i < size; i++) {
if(i == 0 || list.get(i - 1) != list.get(i)) {
rank[m++] = list.get(i);
}
}
for(int i = 1; i < cnt; i++) {
int x1 = Arrays.binarySearch(rank, 0, m, x[i - 1]);
int y1 = Arrays.binarySearch(rank, 0, m, y[i - 1]);
int x2 = Arrays.binarySearch(rank, 0, m, x[i]);
int y2 = Arrays.binarySearch(rank, 0, m, y[i]);
for(int a = x1; a <= x2; a++) {
for(int b = y1; b <= y2; b++) {
board[a][b] = (i + 1) / 2;
}
}
}
int tx = Arrays.binarySearch(rank, 0, m, x[cnt - 1]);
int ty = Arrays.binarySearch(rank, 0, m, y[cnt - 1]);
int ans = board[tx][ty];
System.out.println(ans == 0 ? -1 : ans);
}
}