1235. 付账问题(贪心，均值不等式)

 贪心:

设ave为所有人要付的平均数  ，为  s/n

设t为  (当前还没有付的钱/剩下没付的人)== (s-b1-b2...bi)/(n-i+1)

那么我们的贪心操作是

 证明：

 均值不等式：当且仅当c==d时取最小

既然要保证钱能够全部付完，那么t是要在每个人付完帐后都更新的，不能一直是ave，因为前面的人付完帐后，如果他的钱

这里为什么是每人付t元，而不是有人付ave元，其他的人多付一点呢？

因为 

#include 
#include 
#include 
using namespace std;
const int N = 5e5 + 5;
double a[N];    //本题需要开浮点数int main()
{int n;double s;cin >> n >> s;for (int i = 0;i < n;i++)cin >> a[i];sort(a, a + n);double ave = s / n;double res = 0;for (int i = 0;i < n;i++){   //由于下标0开始，分母不需要+1double t = s / (n - i);//t需要每次都更新if (a[i] <= t){s -= a[i];res += (a[i] - ave)*(a[i]-ave);}else{s -= t;   //减掉t就可以res += (t - ave)*(t-ave);}}printf("%.4lf", sqrt(res / n));
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！