小红的点赞贪心题解

题目

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

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

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

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

样例输入：

1
2

3
3 1 4

样例输出：

1
2
3

9
15
8

思路

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

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

首先明确一点，对于$a[i]$来说，要想最终数组总和最小，肯定是$a[i]$增加1，其余数增加1，以此循环。那么对于$a[i]$来说，只要找出它的最终值就好了。如果找到了他的最终值$num$，答案即为

上面的公式仅适合于$a[i]\neq mx$的情况，$a[i]=mx$时直接输出$sum$。

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

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

这种情况的前提是$a[i]$增长到$mx$的增加次数小于等于其他所有数增长到$mx$的总增加次数，也就是

这种情况的临界值就是$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$，那么经过

次后，$a[i]$的值将第一次大于等于其余所有数的值，这也是$a[i]$的最终值。也就是说，经过$cycle-1$次循环后$a[i]$的值还小于其余所有数最大值，经过$cycle$次循环后$a[i]$的值就大于其余所有数最大值了。

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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%。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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)