倪文迪陪你学蓝桥杯2021冬休み毎日一题:1.22日(2018省赛A组第10题)

2021年冬休み毎日1題、2017~2019年の省試合本題.本文の内容は倪文迪(華東理工大学コンピュータ学部ソフトウェア192クラス)と羅勇軍先生から提供された.次の毎日の問題は、新しいブログを送ります.毎日ブログのブルーブリッジカップのコラムを見てください.https://blog.csdn.net/weixin_43914593/category_10721247.html
C++、Java、Pythonの3言語のコードを提供します.
文書ディレクトリ

1、題名説明

2、題解

3、Pythonコード

4、C++コード

5、Javaコード

2018省試合A組第10題「倍数問題」、タイトルリンク:http://oj.ecustacm.cn/problem.php?id=1367 https://www.dotcpp.com/oj/problem2278.html
1、テーマの説明
何人かで食事に出かけるのはよくあることだ.しかし、会計をするとき、よく争いが起こります.今、n人が食事に出かけています.彼らは全部でS元を消費しました.そのうちi人目はai元を持っています.幸いなことに、すべての人が持っているお金の総数は十分です.しかし、今問題が来ました.一人当たりいくらかかりますか.公平のために、私たちは総支払い量がちょうどSであることを前提に、最後に一人一人が払うお金の基準差が最も小さいことを望んでいます.ここでは、一人一人が支払うお金の数は任意の非負の実数、すなわち1銭の整数倍ではないことを約束します.最小の標準差を出力する必要がありますか?標準差の紹介:標準差は複数の数とそれらの平均数の差の平方平均数で、一般的にこれらの数の間の「偏差がどれだけ大きいか」を描くために使用されます.形式的に言えば、i番目の個人が払うお金をb i bとする.i bi元では、標準差は、  x=1 nΣi=1 n(b i−1 nΣi=1 nb i)2 x=sqrt{frac 1 nsum_{i=1}^n(b_i−frac 1 nsum_{i=1}^nb_i)^2}x=n 1Σi=1 n(bi−n 1Σi=1 nbi)2入力:最初の行は2つの整数n、Sを含む;2行目はn個の非負の整数a 1,n ≤ 5 × 10^5, 0 ≤ ai ≤ 10^9. 出力:最小の標準差を出力し、四捨五入して4桁の小数を保持します.正解は10^−9を加算または減算した後、四捨五入の結果が変化しないことを保証する.
2、問題解
式の中に2つの和を求めるのか、それともネストされているのか、少し煩わしい.さらによく見ると、実は後の和がSなので、式は、 x=1 nΣi=1 n(b i−S n)2 x=sqrt{frac 1 nsum_{i=1}^n(b_i−frac Sn)^2}x=n 1Σi=1 n(bi−nS)2 もし一人一人が持っているお金が十分であれば、一人当たりはまったく同じで、b i=S n=a v g b_i=frac Sn=avg bi=nS=avgであれば簡単であり、x=0 x=0 x=0となる.しかし、いつもお金が足りない人がいるので、二つの状況に分けられます.i ai​.   (2)i i i番目の人が持っているお金は平均数a v g avgより多いので、彼はもっと露店することができます.  基本手順は、  (1)対a i a_i aiは小さいから大きいまで並べ替えます;前の一部の人のお金が足りないなら、彼らのすべてのお金を出します.  (3)前の人が出したお金を総支払額から差し引いて、残りのお金はS’S’S’、後の人の平均お金はa v g’avg’avg’です.  (4)後の一部の人はお金が多くて、彼らはもっと出します.どうやって出るの?この部分の人も2種類に分けられます:1)お金持ちですが、彼のお金もa v g'avg'avg'に足りないので、彼のお金は全部出さなければなりません.2)とてもお金持ちで、いくらやっても余裕がある.
3、Pythonコード

from math import *
n, s = map(int,input().split())
a = list(map(int,input().split()))
a.sort()

avg = s/n
sum = 0
for i in range(n):
     if a[i]*(n-i) < s:
          sum += pow(a[i]-avg,2)
          s -= a[i]
     else:
          cur_avg = s/(n-i);      #       
          sum += pow(cur_avg-avg,2)*(n-i)
          break
print('{:.4f}'.format(sqrt(sum/(n))))

4、C++コード

#include 
using namespace std;
const int M=5e5;

long long a[M];
int main(){
     
    int n;  long long s;   scanf("%d %ld",&n,&s);
    for(int i=1;i<=n;i++)  scanf("%ld",&a[i]);

    sort(a+1,a+n+1);     //  ，    
    double avg=1.0*s/n;  //   
    double sum=0.0;
    for(int i=1;i<=n;i++){
     
        if(a[i]*(n+1-i)<s){
          //         ：（1）       ，（2）     ，       
            sum+=(a[i]-avg)*(a[i]-avg);
            s-=a[i];            //      
        }
        else{
                         //         ：    ，        
            double cur_avg=1.0*s/(n+1-i);  //       
            sum += (cur_avg-avg)*(cur_avg-avg)*(n+1-i);
            break;
        }
    }
    printf("%.4f",sqrt(sum/n));
    return 0;
}

5、Javaコード

//http://oj.ecustacm.cn/ User: 182208202103
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
     
    public static void main(String args[]) throws FileNotFoundException {
     
        int n,i;
        long S;
        double ans=0,avg;
        Scanner input=new Scanner(System.in);
        n=input.nextInt();
        S=input.nextLong();
        long a[]=new long[n];
        for(i=0;i<n;i++) {
     
            a[i]=input.nextLong();
        }
        Arrays.sort(a);
        avg=(double)S/n;
        for(i=0;i<n;i++) {
     
            if(S<=(n-i)*a[i]) {
     
                ans+=(n-i)*Math.pow((double)S/(n-i)-avg,2);
                break;
            }
            ans+=Math.pow(a[i]-avg,2);
            S-=a[i];
        }
        System.out.printf("%.4f
",Math.sqrt(ans/n));
    }
}