C. Robin Hood in Town思考与理解

C. Robin Hood in Town

• 首先就是得思考一个问题：如何快速找到有多少个数严格小于平均数的一半？答案是显而易见的，二分，所以我们需要进行升序排序
• 考虑题目给出的特殊情况当n=1或n=2的时候，直接输出-1即可
• 那么对于可以通过增加x来判断满足最小的x的问题，这里就转换为，如何快速增加x,然后逐一判断这个x所带来的影响？
  • 直接暴力的做法肯定是x从0开始，逐个+1显而易见，这样十分慢
  • 正确的做法是直接使用二分，这里就要考虑这个二分的范围了，最小肯定是0，那么最大是多少？假设n全部放在一个测试用例，那么考虑到最大的数是10**6,n的最大范围2*10**5，如果开始的全部的n都是1，那么我们得将一半的数全部变为最大也就是10**11

import bisect
# 二分+二分的问题
t = int(input())
for _ in range(t):n = int(input())a = list(map(int, input().split()))if n == 1 or n == 2:print(-1)continuea.sort()asum = sum(a)# aver = asum / n# index = bisect.bisect_left(a, aver/2)# if index > n // 2:#     print(0)#     continue# 接下来怎么办？# 增加数的问题，具有二分的性质# 考虑增加的数量为middef check(mid):a[-1] += midtmpsum = asum + midaver = tmpsum / nindex1 = bisect.bisect_left(a, aver/2)a[-1] -= midreturn index1 > n // 2l,r = 0,10**12res = float('inf')while l<=r:mid = (l+r)//2if check(mid):res = min(res,mid)r = mid - 1else:l = mid + 1print(res)