题目链接

1235. 付账问题

几个人一起出去吃饭是常有的事。

但在结帐的时候，常常会出现一些争执。

现在有 \(n\) 个人出去吃饭，他们总共消费了 \(S\) 元。

其中第 \(i\) 个人带了 \(a_i\) 元。

幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？

为了公平起见，我们希望在总付钱量恰好为 \(S\) 的前提下，最后每个人付的钱的标准差最小。

这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 \(1\) 分钱的整数倍。

你需要输出最小的标准差是多少。

标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。

形式化地说，设第 \(i\) 个人付的钱为 \(b_i\) 元，那么标准差为 :

输入格式

第一行包含两个整数 \(n、S\)；

第二行包含 \(n\) 个非负整数 \(a_1, …, a_n\)。

输出格式

输出最小的标准差，四舍五入保留 \(4\) 位小数。

数据范围

\(1≤n≤5×10^5,\)
\(0≤a_i≤10^9,\)
\(0≤S≤10^{15}\)。

输入样例1：

5 2333
666 666 666 666 666

输出样例1：

0.0000

输入样例2：

10 30
2 1 4 7 4 8 3 6 4 7

输出样例2：

0.7928

解题思路

贪心

贪心策略：先将数组排序，依次遍历，如果当前数小于平均数，则该数全选上，差值由后面的数平摊

证明：
首先有均值不等式：若 \(x_1+x_2+...+x_n=s\)，则 \(\frac{x_1^2+x_2^2+...+x_n^2}{n}\geq (\frac{x_1+x_2+...+x_n}{n})^2\) 当且仅当 \(x_1=x_2=...=x_n\) 时 \(=\) 成立
为了防止大的数能被利用到，而小的数又能充分利用，即大的数影响不大到小的数，因为大的数影响小的数只会使答案变差，所以先排序，对于当前数 \(a_i\)，有两种情况：

• \(a_i\geq avg\) 时，由均值不等式选 \(avg\)

• \(a_i< avg\) 时，选 \(a_i\)，反证：如果不选 \(a_i\)，即选择一个数 \(x<a+i\)，假设 \(a_i-x\) 差距由后面某个数 \(b_i\) 来弥补，显然这个差距应该越小越好，即 \(a_i=x\)

• 时间复杂度：\(O(nlogn)\)

代码

// Problem: 付账问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/1237/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=5e5+5;
int n,a[N];
long double s;
int main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    long double avg=s/n;
    long double res=0;
    for(int i=1;i<=n;i++)
    {
        long double cur=s/(n-i+1);
        if(a[i]<cur)cur=a[i];
        res+=(cur-avg)*(cur-avg);
        s-=cur;
    }
    printf("%.4Lf",sqrt(res/n));
    return 0;
}