摘要
Title: 1235. 付账问题
Tag: 均值不等式、贪心
Memory Limit: 64 MB
Time Limit: 1000 ms

1235. 付账问题

题意

见原题
思路

采用贪心的策略，让所有人出的钱越接近平均数 $\frac{S}{n}$ 越好
- 平均数是随着变的！
- 当 $a[i] < \frac{S}{n}$ ，那么就让他出 $a[i]$ ，同时让 $S - a[i]$ ，让后面的人去平摊这个新的 $S$
- 当 $a[i] \ge \frac{S}{n}$ ，那么就让他出 $avg$ 即可，注意此时的平均数是当时的平均数

代码

python float精度不够，如果用Decimal会超时

'''
Author: NEFU AB-IN
Date: 2022-03-30 17:07:11
FilePath: \ACM\Acwing\1235.py
LastEditTime: 2022-03-30 17:11:32
'''
from decimal import Decimal

n, S = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * (n + 1)

tmp = S / n
a.sort()

for i in range(n):
    avg = S / (n - i)
    if a[i] < avg:
        b[i] = a[i]
        S -= a[i]
    else:
        b[i] = avg
        S -= avg
s = 0.0

for i in range(n):
    s += (b[i] - tmp)**2

s = (s / n)**0.5

print(f"{s:.4F}")

这版能过，因为当 $b_i \ge ave$ 时，后面就都是这个，所以直接乘即可，而且这个直接加，精度损失小

'''
Author: NEFU AB-IN
Date: 2022-03-30 19:22:26
FilePath: \ACM\Acwing\1235.1.py
LastEditTime: 2022-03-30 19:22:27
'''
n, s = map(int, input().split())  #从键盘输入人数和消费的金额
a = list(map(int, input().split()))  #将键盘输入的转换为列表
ave = s / n  #计算平均值
a.sort()  #排序
b = 0
for i in range(n):
    if a[i] <= s / (n - i):
        b += pow(a[i] - ave, 2)  #计算平方差
    else:
        b += pow(s / (n - i) - ave, 2) * (n - i)
        break
    s -= a[i]

b = (b / n)**0.5
print("{:.4f}".format(b))  #输出最小标准差

1235. 付账问题

题意

思路

代码