小红书笔试 第二次做还是没ak

第一题 100%

选 k 个支持度最高的粉丝送礼物，点赞一点支持，收藏两点支持。优先级队列。

    static void solve() throws IOException {
        int n = in.nextInt(), k = in.nextInt();
        int[][] a = new int[n + 1][3];
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int score1 = o1[1] + o1[2] * 2, score2 = o2[1] + o2[2] * 2;
                if (score1 != score2) {
                    return score2 - score1;
                } else if (o1[2] != o2[2]) {
                    return o2[2] - o1[2];
                } else {
                    return o1[0] - o2[0];
                }
            }
        });
        for (int i = 1; i <= n; i++) {
            a[i][0] = i;
            a[i][1] = in.nextInt();
            a[i][2] = in.nextInt();
            pq.offer(a[i]);
        }
        int[] ans = new int[k];
        while (k-- > 0) {
            int[] p = pq.poll();
            ans[k] = p[0];
        }
        Arrays.sort(ans);
        for (int id : ans) {
            out.print(Integer.toString(id) + ' ');
        }
    }

第二题 100%

粉丝数转移，背包问题，n 个粉丝群，每个粉丝群可转移 a[i]/2 个粉丝，也可以选一个粉丝群转移 a[i] 个粉丝，求获得目标粉丝数所需的最少粉丝群数量。

    static void solve() throws IOException {
        int n = in.nextInt(), x = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        int ans = func(a, -1, x);
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, func(a, i, x) + 1);
        }
        out.println(ans == 0x3f3f3f3f ? -1 : ans);
    }

    static int func(int[] a, int idx, int target) {
        if (idx != -1) target -= a[idx];
        if (target < 0) return 0x3f3f3f3f;
        int n = a.length;
        int[] dp = new int[target + 1];
        Arrays.fill(dp, 0x3f3f3f3f);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            if (i == idx + 1) continue;
            int val = a[i - 1] / 2;
            for (int j = target; j >= val; j--) {
                dp[j] = Math.min(dp[j], dp[j - val] + 1);
            }
        }
        return dp[target];
    }

第三题 82%

每篇文章成为n篇文章中点赞数最高的之一时的最小点赞数和，限制：每给一篇文章点赞一次后必须要给其它文章点赞一次才能继续点赞该篇文章。二分答案，但是只过了 82%。这题的数学公式解法是怎样的呢？

    static void solve() throws IOException {
        int n = in.nextInt();
        long[] a = new long[n];
        long sum = 0, mx = 0;
        for (int i = 0; i < n; i++) {
            a[i] = in.nextLong();
            sum += a[i];
            mx = Math.max(mx, a[i]);
        }
        for (int i = 0; i < n; i++) {
            if (a[i] >= mx) {
                out.println(sum);
            } else {
                long remain = mx * (n - 1) - (sum - a[i]) + 1;
                if (mx - a[i] <= remain) {
                    out.println(sum + (mx - a[i]) * 2 - 1);
                } else {
                    // long tmpAi = a[i] + remain;
                    // long curSum = mx * (n - 1) + tmpAi;
                    // long x = (n - 1) * (mx - tmpAi) / (n - 2);
                    // out.println(curSum + 2 * x);
                    long left = -1, right = mx * n + 1;
                    while (left + 1 < right) {
                        long mid = left + (right - left) / 2;
                        if (check(mid, sum, a[i], mx, n)) {
                            right = mid;
                        } else {
                            left = mid;
                        }
                    }
                    out.println(sum + 2 * right - 1);
                }
            }
        }
    }

    private static boolean check(long x, long sum, long ai, long mx, int n) {
        return ai + x >= (double) (sum - ai + x - 1) / (n - 1);
    }