Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

ApolloChang同学的解题思路

Posted by ApolloChang at 2011-02-12 17:05:38 on Problem 2646
我看了同学们的讨论,网上公布了一段代码如下:
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator