蓝桥杯样例可以过但是没得分

Question

题目是# [蓝桥杯 2018 省 A] 付账问题

题目描述

几个人一起出去吃饭是常有的事。但在结帐的时候，常常会出现一些争执。

现在有 $n$ 个人出去吃饭，他们总共消费了 $S$ 元。其中第 $i$ 个人带了 $a_i$ 元。幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？

为了公平起见，我们希望在总付钱量恰好为 $S$ 的前提下，最后每个人付的钱的标准差最小。这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 $1$ 分钱的整数倍。你需要输出最小的标准差是多少。

标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。形式化地说，设第 $i$ 个人付的钱为 $b_i$ 元，那么标准差为 $s=\sqrt{\frac{1}{n}\sum_{i=1}^n(b_i-\frac{1}{n}\sum_{i=1}^n b_i)}$

输入格式

第一行包含两个整数 $n$、$S$；

第二行包含 $n$ 个非负整数 $a_1,\cdots,a_n$。

输出格式

输出到标准输出。

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

保证正确答案在加上或减去 $10^{-9}$ 后不会导致四舍五入的结果发生变化。

样例 #1

样例输入 #1

5 2333
666 666 666 666 666

样例输出 #1

0.0000

样例 #2

样例输入 #2

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

样例输出 #2

0.7928

提示

【样例解释】

1. 每个人都出 2333/5 元，标准差为 0。

【数据约定】

对于 $10%$ 的数据，所有 $a_i$ 相等；

对于 $30%$ 的数据，所有非 $0$ 的 $a_i$ 相等；

对于 $60%$ 的数据，$n \le 1000$；

对于 $80%$ 的数据，$n \le 10^5$；

对于所有数据，$n \le 5 \times 10^5,0 \le a_i \le 10^9$。

#include<iostream>
#include<algorithm>
#include<cmath>
#define double long double
using namespace std;
int main(){
    int n,S;
    double pm,bzc = 0;
    double v[500005];
    cin>>n>>S;
    pm = S*1.0/n;
    for(int i = 0;i < n;i++){
        cin>>v[i];
    }
    sort(v,v+n);
    int k = n;
    double pj = pm,re = S;
    for(int i = 0;i < n;i++){
        if(v[i] > pj) v[i] = pj;
        k--;
        re-=v[i];
        pj = re*1.0/k; 
    }
    for(int i = 0;i < n;i++){
        bzc += (v[i]-pm)*(v[i]-pm);
    }    
    printf("%.4lf",sqrt(bzc/n));
}

Answer 1

xxiao_9 上午好☀️☀️☀️️
本答案参考ChatGPT-3.5

问题分析：

蓝桥杯的题目要求计算在总付钱量恰好为S的前提下，最后每个人付的钱的标准差最小。为了计算标准差，需要先计算每个人付的钱数。

解决方案：

1. 读入n和S，以及n个人带的钱数a_i。
2. 计算所有人带的钱数的平均值pm=S/n。
3. 对带的钱数进行排序。
4. 设定初值，k为总人数，pj为pm，re为S。
5. 从小到大遍历带的钱数，如果当前带的钱数大于pj，将其设置为pj；更新re为re-v[i]，k为k-1，pj为re/k。
6. 计算标准差bzc，其中bzc的初值为0，遍历n次，每次计算(v[i]-pm)*(v[i]-pm)，然后将结果累加到bzc中。
7. 最后将bzc除以n，开方得到标准差s。
8. 将s输出，四舍五入保留4位小数。

代码修改： 将最后的printf函数改为cout，保留4位小数输出。

修改后的代码如下：

#include<iostream>
#include<algorithm>
#include<cmath>
#define double long double
using namespace std;
int main(){
    int n,S;
    double pm,bzc = 0;
    double v[500005];
    cin>>n>>S;
    pm = S*1.0/n;
    for(int i = 0;i < n;i++){
        cin>>v[i];
    }
    sort(v,v+n);
    int k = n;
    double pj = pm,re = S;
    for(int i = 0;i < n;i++){
        if(v[i] > pj) v[i] = pj;
        k--;
        re-=v[i];
        pj = re*1.0/k; 
    }
    for(int i = 0;i < n;i++){
        bzc += (v[i]-pm)*(v[i]-pm);
    }    
    cout<<fixed;
    cout.precision(4);
    cout<<sqrt(bzc/n)<<endl;
}

希望对你有帮助。