小红书笔试 2/3 第三题0%

第一题

数组随机移除一个元素，求两次移除刚好是左右两端的概率

    static void solve() throws IOException {
        int n = in.nextInt();
        double res = 1.0;
        // if (n == 2) {out.printf("%.10f\n", res); return;}
        // 1/n * 1/(n-1) * C(2, 1)
        res = 2.0 / n / (n - 1);
        out.printf("%.10f\n", res);
    }

第二题

    static void solve() throws IOException {
        int n = in.nextInt();
        int x = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) { a[i] = in.nextInt(); }
        Arrays.sort(a);
        // 暴力做 使用多次推荐和不使用多次推荐都求一次 取最小
        // 不使用多次推荐即为背包, 若使用多次推荐也可以作为背包问题求解（预设背包容量）
        int ans = func(a, -1, x);
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, func(a, i, x));
        }
        out.println(ans == 0x3f3f3f3f ? -1 : ans);
    }

    static int func(int[] a, int idx, int x) {
        int n = a.length;
        int use = 0;
        if (0 <= idx && idx < n && x >= a[idx]) {
            x -= a[idx];
            use++;
        }
        // dp[i][j] 表示在[0, i]中选物品装满容量为j的背包所需的最少物品数
        int[] dp = new int[x + 1];
        for (int i = 1; i <= x; i++) { dp[i] = 0x3f3f3f3f; }
        for (int i = 1; i <= n; i++) {
            if (i  == (idx + 1)) continue;
            int w = a[i - 1] / 2;
            for (int j = x; j >= w; j--) {
                dp[j] = Math.min(dp[j], dp[j - w] + 1);
            }
        }
        return dp[x] + use;
    }

第三题

写的 if else 屎山 最后几分钟排查逻辑错误也没排查出来

看用例才知道点赞数允许同时最大，所以 maxCnt 后面没用上，代码逻辑如下：

1、如果 a[i] 是 max 直接输出 sum

2、a[i] 不是 max ，计算其它数不超过 max 时可增加多少，记作 cnt，如果 cnt >= max - a[i] , 那么 让 a[i] 增加到与 max 一样大即可，所以输出 sum + (max - a[i]) * 2

3、如果 cnt < max - a[i]，先把能增加的 cnt 全加上 ，此时 a[i] = a[i] + cnt ，sum = sum + cnt * 2 其余数均等于 max

列出方程 a[i] + x >= (sum + x) / (n - 1) 解出 x 即可

最后输出 sum + cnt * 2 + x

但第三步逻辑有点问题，用例输出 9, 16, 8 16 比 15 大了 1。求大佬解惑！

    static void solve() throws IOException {
        // 贪心 需要的信息 其取 a[i] 后数组中的最大值 除去a[i]后数组的和
        int n = in.nextInt();
        int[] a = new int[n];
        int max = -1, maxCnt = 0;
        long sum = 0;
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
            if (a[i] > max) {
                max = a[i];
                maxCnt = 1;
            } else if (a[i] == max) {
                maxCnt++;
            }
            sum += a[i];
        }
        if (n == 1) { out.println(a[0]); }
        if (n == 2) {
            if (a[0] < a[1]) { out.println(-1); out.println(a[0] + a[1]); }
            else if (a[0] == a[1]) { out.println(a[0] + a[1]); out.println(a[0] + a[1]); }
            else { out.println(a[0] + a[1]); out.println(-1); }
        }
        for (int i = 0; i < n; i++) {
            if (a[i] == max) {
                out.println(maxCnt == 1 ? sum : sum);
            } else {
                long cnt = (long) (n - 1) * max - (sum - a[i]);
                if (cnt >= max - a[i]) {
                    out.println(sum + ((long) max - a[i]) * 2);
                } else { 
                    long x = (sum + cnt * 2 - (long) a[i] * (n - 1)) / (n - 1);
                    out.println(sum + cnt * 2 + x);
                }
            }
        }
    }