2024.9.5-XM

A. 题目链接

算法标签：枚举、数据结构。

思路：枚举一遍a数组和b数组的每一个数字，判断是用 a[i] + b[i]，还是以 a[i] 或 b[i]当作最大值（可以把a和b丢到平衡树里）。

 static class PII {
        int value;
        int index;

        public PII(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }


    public static void solve() throws IOException {
        int n = in.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) a[i] = in.nextInt();
        for (int i = 0; i < n; i++) b[i] = in.nextInt();

        TreeSet<PII> tset1 = new TreeSet<>((x, y) -> x.value - y.value);
        TreeSet<PII> tset2 = new TreeSet<>((x, y) -> x.value - y.value);
        for (int i = 0; i < n; i++) {
            tset1.add(new PII(b[i], i));
            tset2.add(new PII(a[i], i));
        }
        long ans = Long.MAX_VALUE / 2;
        for (int i = 0; i < n; i++) {
            int c1 = a[i] + b[i];
            PII ceiling = tset1.ceiling(new PII(a[i], 0));
            ans = Math.min(ans, c1);
            if (ceiling == null) {
                ans = Math.min(ans, a[i]);
            }
            if (ceiling != null && ceiling.index != i) {
                ans = Math.min(ans, ceiling.value);
            }

            PII ceiling2 = tset2.ceiling(new PII(b[i], 0));
            if (ceiling2 == null) {
                ans = Math.min(ans, b[i]);
            }
            if (ceiling2 != null && ceiling2.index != i) {
                ans = Math.min(ans, ceiling2.value);
            }
        }
        out.println(ans);
    }

B. 题目链接

算法标签：动态规划、数学。

思路：最后的数组总和 s要是x的倍数，所以 s % x = 0，并且(a + b + c) % x  == ((a % x) + (b % x) + (c % x))。对于每一个a[i]，有2种选择：

1. 不删除a[i]，dfs(i + 1,  (v + a[i]) % x)。
2. 删除a[i]，dfs(i + 1, v) + 1，或者a[i] + 1，dfs(i + 1, (v + a[i] + 1) % x) + 1。

	static int n, x;
    static int[] a;
    static int[][] dp = new int[1001][1001];
    static final int INF = Integer.MAX_VALUE / 2;


    // (a + b + c) % x == ((a % x) + (b % x) + (c % x))
    static int dfs(int i, int v) {
        if (i >= n) {
            return v % x == 0 ? 0 : INF;
        }
        if (dp[i][v] != -1) return dp[i][v];
        // 不删除
        int res = dfs(i + 1, (v + a[i]) % x);
        // 删除 还是 +1
        int op1 = dfs(i + 1, v) + 1;
        int op2 = dfs(i + 1, (v + a[i] + 1) % x) + 1;
        res = Math.min(res, Math.min(op1, op2));
        return dp[i][v] = res;
    }

    public static void solve() throws IOException {
        n = in.nextInt();
        x = in.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) a[i] = in.nextInt();
        for (int[] d : dp) Arrays.fill(d, -1);

        int res = dfs(0, 0);
        out.println(res);
    }