返回题解分享
讨论 / 题解分享/ 帖子详情

拼十字(编程题) - 题解

视频中标准程序代码如下:

import java.util.*;

class Main {
    static final int N = 100010;
    static int[][] tree = new int[3][N];

    static void add(int id, int p) {
        for (int i = p; i < N; i += (i & -i)) {
            tree[id][i] += 1;
        }
    }

    static int get(int id, int p) {
        int s = 0;
        for (int i = p; i > 0; i -= (i & -i)) {
            s += tree[id][i];
        }
        return s;
    }

    static class Node {
        int x, y, z;

        Node(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }

    static class NodeComparator implements Comparator<Node> {
        public int compare(Node a, Node b) {
            return (a.x == b.x) ? (a.y > b.y ? -1 : (a.y == b.y ? 0 : 1)) : (a.x > b.x ? -1 : 1);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int ans = 0;
        int mod = (int) 1e9 + 7;
        Node[] a = new Node[N];
        for (int i = 1; i <= n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int z = scanner.nextInt();
            a[i] = new Node(x, y, z);
        }
        Arrays.sort(a, 1, n + 1, new NodeComparator());

        for (int i = 1; i <= n; i++) {
            if (a[i].z != 0) ans += get(0, a[i].y - 1);
            if (a[i].z != 1) ans += get(1, a[i].y - 1);
            if (a[i].z != 2) ans += get(2, a[i].y - 1);

            ans %= mod;
            if (a[i].z == 0) add(0, a[i].y);
            if (a[i].z == 1) add(1, a[i].y);
            if (a[i].z == 2) add(2, a[i].y);
        }
        System.out.println(ans % mod);
    }
}
0 回复 0 转发 1 喜欢 9 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!