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