小红的点赞（二）

[题目链接](https://www.nowcoder.com/practice/b5bd2d0d30154ae6bbd11b25b56dbd6d)

思路

本题的关键在于理解"不会出现一个笔记点赞数连续增加"这一约束。

分析

设所有笔记初始赞数为 $a_1, a_2, \ldots, a_n$ ，总和为 $S$ ，最大值为 $M$ 。

对于笔记 $i$ ，我们需要让它的赞数达到某个目标值 $T$ （ $T \ge M$ ），使得没有其他笔记超过 $T$ 。

假设笔记 $i$ 需要增加 $D = T - a_i$ 次赞。由于不能连续给同一笔记点赞， $D$ 次点赞之间需要穿插至少 $D - 1$ 次对其他笔记的点赞。

这 $D - 1$ 次"其他点赞"分配给其他 $n - 1$ 个笔记，设笔记 $j$ （ $j \ne i$ ）额外获得 $x_j$ 次点赞，则需要满足：

$ $\sum_{j \ne i} x_j = D - 1, \quad a_j + x_j \le T \text{（即 } x_j \le T - a_j \text{）}$ $

总可承受上限为 $\sum_{j \ne i}(T - a_j) = (n-1)T - (S - a_i)$ ，所以需要：

$ $D - 1 \le (n-1)T - S + a_i$ $

代入 $D = T - a_i$ 整理得：

$ $T \ge \frac{S - 2a_i - 1}{n - 2} \quad (n \ge 3)$ $

所以当 $n \ge 3$ 时， $T = \max\!\left(M,\; \left\lceil\frac{S - 2a_i - 1}{n - 2}\right\rceil\right)$ ，答案为 $S + 2D - 1$ （ $D > 0$ 时）或 $S$ （ $D = 0$ 时）。

特殊情况

$n = 1$ ：只有一个笔记，已是最大，答案直接为 $a_1$ 。
$n = 2$ ：两个笔记 $a_i$ 和 $a_j$ 。每次给 $i$ 加赞后必须给 $j$ 加赞，两者交替增长。当 $a_j - a_i > 1$ 时， $i$ 永远追不上 $j$ ，输出 $-1$ 。否则只需至多 1 步即可追平。

举例

以样例 $[3, 1, 4]$ 为例， $S = 8$ ， $M = 4$ ：

笔记	$a_i$	$T$	$D$	答案
1	3	$\max(4, \lceil 1/1 \rceil) = 4$	1	$8 + 1 = 9$
2	1	$\max(4, \lceil 5/1 \rceil) = 5$	4	$8 + 7 = 15$
3	4	$\max(4, \lceil{-1}/1 \rceil) = 4$	0	$8$

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n);
    long long S = 0, mx = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        S += a[i];
        mx = max(mx, a[i]);
    }
    if(n == 1){
        cout << a[0] << "\n";
        return 0;
    }
    for(int i = 0; i < n; i++){
        if(n == 2){
            int j = 1 - i;
            if(a[j] - a[i] > 1){
                cout << -1 << "\n";
            } else {
                long long T = max(a[i], a[j]);
                long long D = T - a[i];
                if(D == 0) cout << S << "\n";
                else cout << S + 2*D - 1 << "\n";
            }
        } else {
            long long num = S - 2*a[i] - 1;
            long long den = n - 2;
            long long T2;
            if(num <= 0){
                T2 = 0;
            } else {
                T2 = (num + den - 1) / den;
            }
            long long T = max(mx, T2);
            long long D = T - a[i];
            if(D == 0) cout << S << "\n";
            else cout << S + 2*D - 1 << "\n";
        }
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        long[] a = new long[n];
        long S = 0, mx = 0;
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(st.nextToken());
            S += a[i];
            mx = Math.max(mx, a[i]);
        }
        StringBuilder sb = new StringBuilder();
        if (n == 1) {
            sb.append(a[0]).append("\n");
        } else {
            for (int i = 0; i < n; i++) {
                if (n == 2) {
                    int j = 1 - i;
                    if (a[j] - a[i] > 1) {
                        sb.append(-1).append("\n");
                    } else {
                        long T = Math.max(a[i], a[j]);
                        long D = T - a[i];
                        if (D == 0) sb.append(S).append("\n");
                        else sb.append(S + 2 * D - 1).append("\n");
                    }
                } else {
                    long num = S - 2 * a[i] - 1;
                    long den = n - 2;
                    long T2;
                    if (num <= 0) {
                        T2 = 0;
                    } else {
                        T2 = (num + den - 1) / den;
                    }
                    long T = Math.max(mx, T2);
                    long D = T - a[i];
                    if (D == 0) sb.append(S).append("\n");
                    else sb.append(S + 2 * D - 1).append("\n");
                }
            }
        }
        System.out.print(sb);
    }
}

复杂度分析

时间复杂度： $O(n)$ ，遍历数组一次求和与最大值，再遍历一次计算每个笔记的答案。
空间复杂度： $O(n)$ ，存储输入数组。