文章

付账问题(2018省赛)

付账问题1.png付账问题2.png

贪心 先从小到大排序, 若小于平均数,则全部支付,然后更新平均数 若大于平均数,则后面的人也全部可以支付,直接全部支付平均数即可。

#include<bits/stdc++.h>
using namespace std;
const long long int maxn=5e5+10;
double a[maxn];
int main()
{
    double sum=0,avg=0,s=0,ans,newavg=0;
    long long int n,i,nn;
    cin>>n>>sum;
    nn=n;
    for(i=0;i<n;i++) {
        cin>>a[i];
    }
    avg=1.0*sum/double(n);
    newavg=avg;
    sort(a,a+n);
    for(i=0;i<n;i++){
        if(a[i]*(n-i)<sum){
            ans+=(avg-a[i])*(avg-a[i]);
            sum-=a[i];
        }else {
            double cur=sum/(n-i);
            ans+=(n-i) * ( (cur-avg)*(cur-avg) );
            break;
        }
    }
//    for(i=0;i<n;i++){
//        if(a[i]<newavg){//小于平均数 全部支付 
//            ans+=((avg-a[i])*(avg-a[i]));
//            nn--;
//            sum-=a[i];
//            newavg=sum/double(nn);
//        }else {// 大于等于平均数  支付newavg 
//            ans+=((newavg-avg)*(newavg-avg));
//        }
//    }
    printf("%.4lf\n",sqrt(ans/n));
    return 0;
 }

原题链接

https://www.lanqiao.cn/problems/174/learning/

License:  CC BY 4.0