【蓝桥杯】付款问题—贪心思想求解

题解分析：

如何求标准差：怎么计算标准差呢

https://jingyan.baidu.com/article/f0062228ecda76bbd2f0c85d.html

准备就绪，开始：

1、共需付款 S 元，故每人平均需要付款 S / N ，该值记为 avg；

2、将 N 个人的所持有的钱数按照从少到多排序

3、从钱数最少的人开始遍历，将其所持有的金钱 M 与当前的 avg 值进行比较

        此时若 M < avg：那么该人的钱全部拿来付款；avg 更新（总钱数 - 已付款金额）/ 剩余人数

        若M > avg ：说明从该人开始以后的每个人都有足够的钱用来付款，不进行凑钱补钱的操作

总体思想就是：尽可能的让每个人出的钱都与平均值相接近

//标准差最小 
#include <bits/stdc++.h>
using namespace std;
const int vinf = 5e5+100;
long long int val[vinf];
int main(){
	//输入数据
	long long int n,s;
	scanf("%lld %lld",&n,&s);
	for(int i=1;i<=n;++i){
		scanf("%lld",&val[i]);
	}
	//数组排序
	sort(val+1,val+n+1);
	double avg = 1.0*s/n;   //平均值
	double ans = 0.0; 
	//开始遍历比较
	for(int i=1;i<=n;++i){
		if(val[i]*(n+1-i) < s) {
			ans += (val[i]-avg)*(val[i]-avg);
			s -= val[i];
		}
		else {
			double pavg = 1.0*s/(n+1-i);		
			ans += (pavg-avg)*(pavg-avg)*(n+1-i); 
			break;
		}
	}
	printf("%.4lf",sqrt(ans/n));
	return 0;
}

备注：最后实现的方式与我的略有差别，我的也没有通过测试，暂时就以这个为准！