【铺地毯】这题能离散化吗?MLE 了
查看原帖
【铺地毯】这题能离散化吗?MLE 了
561690
洛谷小灵楼主2022/3/11 11:16

之前其实我用了非离散化的方式过了,最近学习离散化,想问问,这题能不能离散化,我这边是直接 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);
    }
}
2022/3/11 11:16
加载中...