题目链接

小红的点赞（二）

题目描述

小红有 个笔记，初始点赞数分别为 。

点赞数会随时间增加，规则如下：

  1. 每次只有一个笔记的点赞数加 1。
  2. 一个笔记的点赞数增加后，下一个获得点赞的必定是另一个不同的笔记。

对于每一个笔记 （从 1 到 ），我们需要计算一个独立的问题：当笔记 的点赞数首次变为所有笔记中最多（允许并列）时，所有笔记的点赞总和的最小值是多少？

如果某个笔记永远无法成为点赞数最多的笔记，则针对该笔记输出 -1。

解题思路

这是一个需要对每个笔记进行独立分析的最优化问题。核心在于理解“交替点赞”规则对点赞数增长的限制。

核心约束分析

假设我们想让笔记 的点赞数达到某个目标值 ，而它当前的赞数是 。这需要给笔记 点赞 次。

根据“交替点赞”规则，在给笔记 点了第 1 次赞之后，必须先给其他笔记点赞，然后才能给笔记 点第 2 次赞。这个过程会一直持续。这意味着，在给笔记 点 次赞的过程中，至少需要给其他笔记点赞 次（如果 ）。

数学建模

对于一个目标笔记 ，我们希望它最终的点赞数达到 ，并且成为最大值。这意味着：

  1. 笔记 的最终赞数 。
  2. 其他任意笔记 的最终赞数 。
  3. 我们需要找到满足条件的最小的那个最终总和 。

为了让总和最小，我们应该让所有笔记获得的总点赞次数最少。

设笔记 获得了 次赞。 那么其他笔记总共至少需要获得 次赞。

这些 次赞可以分配给其他 个笔记。同时，这些笔记在接受了点赞后，其最终的点赞数也不能超过 。

也就是说，对于任意一个笔记 ，它最多能“吸收”的点赞数是 。

因此，所有其他笔记总共能吸收的点赞数上限（我们称之为“容量”）是 。

要使得目标状态 可行，其他笔记的“总容量”必须足以容纳它们“必须获得”的点赞数。即：

推导目标值 v

我们可以通过解上述不等式来找到 的下限。 令 为初始总赞数 。

不等式变为：

这个不等式给出了 的一个下限。此外， 还必须不小于初始数组中的最大值，我们称之为 max_val。 所以，最小的可行目标值 由这两个下限共同决定。

分情况讨论

上述推导中，我们除以了 ，所以需要对 的情况进行特殊处理。

情况一：

  1. 从不等式 得到 。我们称这个下限为 。

  2. 还必须不小于初始最大值 。

  3. 所以，最终的目标值 。

  4. 计算总点赞增量：

    • 笔记 增加:

    • 其他笔记增加:

  5. 最终总和 = 。

情况二：

设两个笔记为 和 。我们要让 成为最大值。

  • 如果 ，它已经是最大值，总和就是初始总和 。

  • 如果 ，为了让 追上 ， 每增加 1， 也必须增加 1（为了满足交替规则），它们的差值永远不会缩小。唯一的例外是当 只需要增加 1 次时，其他笔记可以不增加。

    • 这只在 时可能发生。 增加 1 变为 （即 的值），此时两者相等。最终状态是 ，总和为 。

    • 如果 ，差值至少为 2， 永远追不上，输出 -1。

情况三：

只有一个笔记，它永远是最大值。总和就是它自己。

代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<long long> a(n);
    long long initial_sum = 0;
    long long max_val = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        initial_sum += a[i];
        if (a[i] > max_val) {
            max_val = a[i];
        }
    }

    if (n == 1) {
        cout << a[0] << endl;
        return 0;
    }

    if (n == 2) {
        // Case for a[0]
        if (a[0] >= a[1]) {
            cout << a[0] + a[1] << endl;
        } else if (a[1] > a[0] + 1) {
            cout << -1 << endl;
        } else { // a[1] == a[0] + 1
            cout << 2 * a[1] << endl;
        }
        // Case for a[1]
        if (a[1] >= a[0]) {
            cout << a[0] + a[1] << endl;
        } else if (a[0] > a[1] + 1) {
            cout << -1 << endl;
        } else { // a[0] == a[1] + 1
            cout << 2 * a[0] << endl;
        }
        return 0;
    }

    // Case for n > 2
    for (int i = 0; i < n; ++i) {
        long long num = initial_sum - 2 * a[i] - 1;
        long long den = n - 2;
        long long min_v_for_ops = 0;
        if (num > 0) {
            min_v_for_ops = (num + den - 1) / den;
        }
        
        long long target_v = max(max_val, min_v_for_ops);
        
        long long likes_i = target_v - a[i];
        long long likes_other = max(0LL, likes_i - 1);
        
        long long ans = initial_sum + likes_i + likes_other;
        cout << ans << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        long initialSum = 0;
        long maxVal = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            initialSum += a[i];
            if (a[i] > maxVal) {
                maxVal = a[i];
            }
        }

        if (n == 1) {
            System.out.println(a[0]);
            return;
        }

        if (n == 2) {
            // Case for a[0]
            if (a[0] >= a[1]) {
                System.out.println(a[0] + a[1]);
            } else if (a[1] > a[0] + 1) {
                System.out.println(-1);
            } else { // a[1] == a[0] + 1
                System.out.println(2 * a[1]);
            }
            // Case for a[1]
            if (a[1] >= a[0]) {
                System.out.println(a[0] + a[1]);
            } else if (a[0] > a[1] + 1) {
                System.out.println(-1);
            } else { // a[0] == a[1] + 1
                System.out.println(2 * a[0]);
            }
            return;
        }

        // Case for n > 2
        for (int i = 0; i < n; i++) {
            long num = initialSum - 2 * a[i] - 1;
            long den = n - 2;
            long minVForOps = 0;
            if (num > 0) {
                minVForOps = (num + den - 1) / den;
            }
            
            long targetV = Math.max(maxVal, minVForOps);
            
            long likesI = targetV - a[i];
            long likesOther = Math.max(0L, likesI - 1);
            
            long ans = initialSum + likesI + likesOther;
            System.out.println(ans);
        }
    }
}

import sys
import math

def solve():
    try:
        n_str = sys.stdin.readline().strip()
        if not n_str: return
        n = int(n_str)
        a = list(map(int, sys.stdin.readline().strip().split()))
    except (IOError, ValueError):
        return

    if n == 1:
        print(a[0])
        return

    initial_sum = sum(a)
    max_val = max(a)

    if n == 2:
        # Case for a[0]
        if a[0] >= a[1]:
            print(a[0] + a[1])
        elif a[1] > a[0] + 1:
            print(-1)
        else: # a[1] == a[0] + 1
            print(2 * a[1])
        # Case for a[1]
        if a[1] >= a[0]:
            print(a[0] + a[1])
        elif a[0] > a[1] + 1:
            print(-1)
        else: # a[0] == a[1] + 1
            print(2 * a[0])
        return

    # Case for n > 2
    for i in range(n):
        num = initial_sum - 2 * a[i] - 1
        den = n - 2
        min_v_for_ops = 0
        if num > 0:
            min_v_for_ops = (num + den - 1) // den
            
        target_v = max(max_val, min_v_for_ops)
        
        likes_i = target_v - a[i]
        likes_other = max(0, likes_i - 1)
        
        ans = initial_sum + likes_i + likes_other
        print(ans)

solve()

算法及复杂度

  • 算法：数学推导 + 分情况讨论

  • 时间复杂度：。

    • 初次计算总和与最大值需要 。

    • 之后对每个笔记进行计算，循环 次，每次计算都是 的。

    • 总的时间复杂度为 。

  • 空间复杂度：，用于存储输入的点赞数数组。