小红的点赞贪心题解O(n)复杂度

题目

小红发布了n个笔记，每个笔记的点赞数为 $a_i$ 。小红观察到，每隔一段时间，某个笔记的点赞数就会加1。但是不会出现一个笔记点赞数连续增加的情况。也就是说，一个笔记赞数加1后，下一个加1的必然是另一个笔记。

现在小红想知道，对于每一个笔记，其赞数变成所有笔记赞数最多时，此时所有的笔记赞数之和的最小值是多少？

输入描述：第一行输入一个正整数n，代表笔记的数量。第二行输入n个正整数 $a_i$ ，代表每个笔记当前的赞数。 $1 ≤ n ≤ 10^5, 1 ≤ a_i ≤ 10^9$

输出描述：输出n行，每行输出一个整数，代表第i个笔记变成所有笔记赞数最多时，此时所有的笔记赞数之和的最小值。特殊的，如果第i个笔记永远无法变成赞数最多，则输出-1。

样例输入：

3
3 1 4

样例输出：

9
15
8

思路

网上很多人对这道题都是二分做的，在此提供一种 $O(n)$ 的贪心做法。

设数组最大值是 $mx$ ，数组的和是 $sum$ ，长度是 $n$ 。

首先明确一点，对于 $a[i]$ 来说，要想最终数组总和最小，肯定是 $a[i]$ 增加1，其余数增加1，以此循环。那么对于 $a[i]$ 来说，只要找出它的最终值就好了。如果找到了他的最终值 $num$ ，答案即为
$(num-a[i]-1)*2+1+sum$
上面的公式仅适合于 $a[i]\neq mx$ 的情况， $a[i]=mx$ 时直接输出 $sum$ 。

显而易见， $a[i]$ 的最终值一定大于等于 $mx$ 。

$a[i]$ 最终值等于 $mx$

这种情况的前提是 $a[i]$ 增长到 $mx$ 的增加次数小于等于其他所有数增长到 $mx$ 的总增加次数，也就是
$sum-(n-1)\times mx \geq mx-a[i]$
这种情况的临界值就是 $sum-(n-1)*mx = mx-a[i]$ ，此时刚好 $a[i]$ 增加到 $mx$ 时，其余所有数也都增长到了 $mx$ 。

$a[i]$ 最终值大于 $mx$

这种情况的前提是 $a[i]$ 增长到 $mx$ 的增加次数大于其他所有数增长到 $mx$ 的总增加次数，此时我们以恰好其余所有数都增加到 $mx$ 为起始状态开始思考，这个起始状态下， $a[i]$ 的值增加到了 $a[i]+(n-1)\times mx-(sum-a[i])$ ， $a[i]$ 和其余数字最大值的差距为 $relative=mx-(a[i]+(n-1)\times mx-(sum-a[i]))$

我们以 $(n-1)\times 2$ 次操作为一次循环，经过这 $(n-1)\times 2$ 操作后， $a[i]$ 的值刚好增加 $n-1$ ，其余所有数的值都刚好增加1，也就是说， $a[i]$ 和其余数最大值的差距缩小了 $n-2$ （类比物理里面的相对速度），既然每次循环二者差距缩小 $n-2$ ，那么经过
$cycle=ceil(relative/(n-2))=(relative+n-3)//(n-2)$
次后， $a[i]$ 的值将第一次大于等于其余所有数的值，这也是 $a[i]$ 的最终值。也就是说，经过 $cycle-1$ 次循环后 $a[i]$ 的值还小于其余所有数最大值，经过 $cycle$ 次循环后 $a[i]$ 的值就大于其余所有数最大值了。

那么，其余数经过 $cycle$ 次循环后，所有数字都等于 $mx+cycle$ ，这就是 $a[i]$ 的最终值。

代码

n = int(input())
aa = list(map(int, input().split()))
s = sum(aa)
mx = max(aa)
for i in range(n):
    if mx == aa[i]:
        print(s)
        continue
    tmp1 = mx * (n - 1) - (s - aa[i])
    if tmp1 < mx - aa[i] and n <= 2: # 无解情况，永远追不上其他元素的最大值
        print(-1)
        continue
    if tmp1 >= mx - aa[i]:  # 最终值就是mx
        print(2 * (mx - aa[i] - 1) + 1 + s)
        continue
    # 最终值大于mx
    rela = mx - (aa[i] + tmp1)
    cycle = (rela + n - 3) // (n - 2)
    final = mx + cycle
    print(2 * (final - aa[i] - 1) + 1 + s)

ps：上面的代码当rela%(n-2)=0时会有问题，代码通过率为90%，下面的代码通过率是100%。

n = int(input())
aa = list(map(int, input().split()))
s = sum(aa)
mx = max(aa)
for i in range(n):
    if mx == aa[i]:
        print(s)
        continue
    tmp1 = mx * (n - 1) - (s - aa[i])
    if tmp1 < mx - aa[i] and n <= 2: # 无解情况，永远追不上其他元素的最大值
        print(-1)
        continue
    if tmp1 >= mx - aa[i]:  # 最终值就是mx
        print(2 * (mx - aa[i] - 1) + 1 + s)
        continue
    # 最终值大于mx
    rela = mx - (aa[i] + tmp1)
    cycle = (rela - 1) // (n - 2)
    remain = rela % (n - 2)
    print(tmp1 * 2 + cycle * (n - 1) * 2 + remain * 2 + 1 + s)