方法思路

1. 核心问题：计算使笔记i成为赞数最多时的最小总赞数
2. 数学分析：
   • 笔记i需要增加到赞数k才能成为最多
   • 由于不能连续点赞同一笔记，每点赞笔记i一次，必须点赞另一笔记一次
   • 可行性条件：k*(n-2) ≥ totalLikes-2*likes[i]-1
3. 解决方案：
   • 对每个笔记，二分查找最小可行k值（或直接用数学公式计算）
   • 特殊处理n=1和n=2的情况
   • 计算最终总赞数：totalLikes + (k-likes[i])*2-1
4. 优化：C++版本使用数学公式直接计算k，避免二分查找，降低时间复杂度

代码实现

Java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        int n = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        
        long[] likes = new long[n];
        long maxLike = 0;
        long totalLikes = 0;
        
        for (int i = 0; i < n; i++) {
            likes[i] = Long.parseLong(input[i]);
            maxLike = Math.max(maxLike, likes[i]);
            totalLikes += likes[i];
        }
        
        // 特殊情况处理
        if (n == 1) {
            out.println(likes[0]);
            out.flush();
            return;
        }
        
        if (n == 2) {
            for (int i = 0; i < 2; i++) {
                if (likes[i] == maxLike) {
                    out.println(totalLikes);
                } else if (likes[i] == maxLike - 1) {
                    out.println(totalLikes + 1);
                } else {
                    out.println(-1);
                }
            }
            out.flush();
            return;
        }
        
        for (int i = 0; i < n; i++) {
            // 如果当前笔记已是最大赞数
            if (likes[i] == maxLike) {
                out.println(totalLikes);
                continue;
            }
            
            // 二分查找最小可行k
            long left = maxLike;
            long right = 2_000_000_000L;
            while (left <= right) {
                long mid = left + (right - left) / 2;
                // 检查是否可行
                if ((mid - likes[i]) <= (n - 1) * mid - (totalLikes - likes[i]) + 1) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            // 计算最终总赞数
            out.println(totalLikes + (left - likes[i]) * 2 - 1);
        }
        
        out.flush();
    }
}

Python

def min_total_likes(n, likes):
    # 计算最大赞数和总赞数
    max_like = max(likes)
    total_likes = sum(likes)
    
    # 特殊情况处理
    if n == 1:
        return [likes[0]]
    
    if n == 2:
        results = []
        for i in range(2):
            if likes[i] == max_like:
                results.append(total_likes)
            elif likes[i] == max_like - 1:
                results.append(total_likes + 1)
            else:
                results.append(-1)
        return results
    
    results = []
    for i in range(n):
        # 如果当前笔记已是最大赞数
        if likes[i] == max_like:
            results.append(total_likes)
            continue
        
        # 二分查找最小可行k
        left, right = max_like, 10**12
        while left <= right:
            mid = (left + right) // 2
            # 检查是否可行
            if (mid - likes[i]) <= (n - 1) * mid - (total_likes - likes[i]) + 1:
                right = mid - 1
            else:
                left = mid + 1
        
        # 计算最终总赞数
        results.append(total_likes + (left - likes[i]) * 2 - 1)
    
    return results

# 读取输入
n = int(input())
likes = list(map(int, input().split()))

# 计算并输出结果
results = min_total_likes(n, likes)
for result in results:
    print(result)

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<long long> likes(n);
    long long maxLike = 0;
    long long totalLikes = 0;
    
    for (int i = 0; i < n; i++) {
        cin >> likes[i];
        maxLike = max(maxLike, likes[i]);
        totalLikes += likes[i];
    }
    
    // 特殊情况处理
    if (n == 1) {
        cout << likes[0] << '\n';
        return 0;
    }
    
    if (n == 2) {
        for (int i = 0; i < 2; i++) {
            if (likes[i] == maxLike) {
                cout << totalLikes << '\n';
            } else if (likes[i] == maxLike - 1) {
                cout << totalLikes + 1 << '\n';
            } else {
                cout << -1 << '\n';
            }
        }
        return 0;
    }
    
    for (int i = 0; i < n; i++) {
        // 如果当前笔记已是最大赞数
        if (likes[i] == maxLike) {
            cout << totalLikes << '\n';
            continue;
        }
        
        // 使用数学方法直接计算k，而不是二分查找
        // 从二分查找条件推导：
        // (k - likes[i]) <= (n - 1) * k - (totalLikes - likes[i]) + 1
        // k - likes[i] <= (n - 1) * k - totalLikes + likes[i] + 1
        // k - likes[i] <= (n - 1) * k - totalLikes + likes[i] + 1
        // k - (n - 1) * k <= -totalLikes + 2 * likes[i] + 1
        // k * (2 - n) <= -totalLikes + 2 * likes[i] + 1
        // k * (n - 2) >= totalLikes - 2 * likes[i] - 1
        // k >= (totalLikes - 2 * likes[i] - 1) / (n - 2)
        
        long long k;
        if (n > 2) {
            // 计算k并向上取整
            k = (totalLikes - 2 * likes[i] - 1 + n - 3) / (n - 2);
            k = max(k, maxLike);
        } else {
            k = maxLike;
        }
        
        // 验证计算出的k是否满足条件
        while ((k - likes[i]) > (n - 1) * k - (totalLikes - likes[i]) + 1) {
            k++;
        }
        
        // 计算最终总赞数
        cout << totalLikes + (k - likes[i]) * 2 - 1 << '\n';
    }
    
    return 0;
}