| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
ApolloChang同学的解题思路我看了同学们的讨论,网上公布了一段代码如下:
#include <iostream>
using namespace std;
double a[1000];
int main()
{
int n;
double avg, big, small;
while(cin >> n && n){
big = small = avg = 0;
for(int i=0; i<n; i++){
cin >> a[i];
avg += a[i];
}
avg /= (double)n;
avg =(int)(avg*100+0.5)/100.0;
for(int i=0; i<n; i++){
if(a[i] <= avg)
big += (avg - a[i]);
else
small -= (avg - a[i]);
}
cout.precision(2);
cout << '$' << fixed << min(big, small) << endl;
}
}
这个代码是可以AC的,但是我当时怎么也不明白里面的道理,事实上,这种做法虽然可以AC但是是错误的,我们可以举一个例子:
当n为8时,输入的数据为10.01 10.01 10.01 10.01 10.01 10.00 6.00 6.00
根据上面的代码,运行结果是5.99但是实际上这是错误的,答案应该为6.00
为此,我的做法是,如果钱数总和不能被人数整除(整除的情况很容易解决),那么就列出两个数,avg2和avg1,这两个数分别是舍弃小数点两位后的数字、舍弃小数点两位后的数字+0.01,之后只好循环一下找到到底有多少个avg1和多少个avg2,最终只要用大于avg1的数减去avg1,同时avg1数字个数减去1, 当avg1的个数用完时,在用大于avg2的数减去avg2,将上述操作结果的和四舍五入即可得到最终结果。这种做法是模拟法,较容易思考.下面附上我的代码:
#include <stdio.h>
#include <math.h>
double a[1000];
int main()
{
bool ifint = false;
int n;
double avg1, avg2, sum, minsum;
while(scanf("%d", &n) != EOF && n != 0)
{
sum = 0;
ifint = false;
for(int i=0; i<n; i++){
scanf("%lf", &a[i]);
sum += a[i];
}
avg1 = sum / (double)n;
if(abs(avg1*100-(int)(avg1*100)) < 0.0000001) ifint = true;
avg2 = (int)(avg1*100)/100.0;
avg1 = avg2+0.01;
if(ifint)
{
minsum = 0;
for(int i = 0; i < n; i++)
{
if(a[i] - avg2 >= -0.000000001)
minsum += abs(a[i] - avg2);
}
minsum = (int)(minsum*100+0.5) / 100.0;
printf("$%.2f\n", minsum);
}
else
{
int bignumber = 0;
for(int i = 0; i < n; i++)
{
if(abs(avg1*(i+1)+avg2*(n-i-1) - sum) < 0.0000001)
{
bignumber = i+1;
break;
}
}
minsum = 0;
for(int i = 0; i < n; i++)
{
if(bignumber > 0 && a[i] - avg1 >= -0.0000001)
{
bignumber--;
minsum += a[i] - avg1;
}
else if(bignumber <= 0 && a[i] - avg2 >= -0.00000001)
{
minsum += a[i] - avg2;
}
}
minsum = (int)(minsum*100+0.5) / 100.0;
printf("$%.2f\n", minsum);
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator