放牧代码和思想
专注自然语言处理、机器学习算法

UVa Q10137: The Trip

模拟类。有点小意思,没什么算法,除了题目有点难理解,所以题目后面有自己写的思路。

Q10137: The Trip

有一群学生组成一个社团,他们每年都会到国外去旅游。过去几年他们已经去过Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, 和 Atlanta。今年春天他们计画到Eindhoven。

学生们都同意旅游所花的钱应该要平均分摊,但是实际上在付钱的时候却不太方便。所以有人先付车钱,有人付餐费,有人付门票费用。等到旅游结束后,每个人统计自己出了多少钱,然后出的比较少的人必须拿钱给出的比较多的人,使得每个人所出的钱都相等,如果无法每个人出的钱相等,最多只能相差一分钱(美金的一分钱,one cent)。你现在的任务就是:给你每个学生旅游时出的钱,请你算出最少有多少钱要交换(就是出的少的人拿钱给出的多的人),使得每个人所出的钱都尽可能接近。

Input

输入含有多组测试资料。

每组测试资料的第一列有1个整数 n,代表学生的人数。接下来的 n 列为每个学生旅游时出的钱,最小单位为一分钱。学生最多不会超过1000人,每个人出的钱不会超过美金$10,000.00元。

n=0代表输入结束,请参考Sample Input。

Output

对每组测试资料输出一列 。输出最少有多少钱要交换,使得每个人所出的钱都尽可能接近。格式请参考Sample Output。

Sample Input Sample Output
3 
10.00 
20.00 
30.00 
4 
15.00 
15.01 
3.00 
3.01 
5 
5000.00 
11.11 
11.11 
11.11 
11.11 
0
$10.00
$11.99
$3991.11

简体中文由Lucky貓的 UVA(ACM)園地转换。

老实说,刚看到这题我不知道它要什么。我以为把钱一统计求平均多退少补不就完了?不过很明显不是这么简单,思考如下两个问题:什么叫平均?除法能保证平均的精确吗?

平均按题目理解并非精确的平均,而是“尽可能接近”。按照最小单位为1分钱来讲,误差在1分钱之内就是对的。

可是这里涉及到除法,不知道是个人心理还是怎么着,很抵触在acm类题目里使用浮点数。也许是因为水平不够吧,浮点数误差不知道怎么处理,所以全部用了整型。

这题什么算法都没有,就一个模拟。首先求两个数,一个平均(向下取整)和平均+1分钱(争取钱的流动量最小),然后定义一个盘子,少给钱的人把少给的钱(按平均算)放到盘子里,多给钱的人从盘子里拿走多给的钱(按平均+1分算)。因为多给的钱和少给的钱的计算标准不一样(这是为了争取钱的流动量最小),盘子的平衡肯定会被打破。所以最后盘子里肯定有多的钱没退给多给钱的人,亦即最后的结果必须加上这个值。至于退给谁,那就不是这个题目的要求范围了。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <iomanip>
using namespace std;

#define MAX 10000

void print_answer(const int& ans)
{
	cout << '$' << ans / 100 << '.' << setw(2) << setfill('0') << ans % 100 << endl;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n = 0;
	while (cin >> n && n)
	{
		int payment[MAX];
		int all = 0;
		for (int i = 0; i < n; ++i)
		{
			int a = 0, b = 0;
			cin >> a;
			cin.get();
			cin >> b;
			payment[i] = a * 100 + b;
			all += payment[i];
		}
		int ave = all / n;
		int ave_more = ave + 1;
		
		int bucket = 0;

		int ans = 0;
		
		for (int i = 0; i < n; ++i)
		{
			if (payment[i] > ave_more)
			{
				int exchange = payment[i] - ave_more;
				bucket -= exchange;
				ans += exchange;
			}
			else if (payment[i] < ave)
			{
				int exchange = ave - payment[i];
				bucket += exchange;
			}
		}

		// shoud give back it to the gays who paid more than ave_more
		if (bucket > 0)
		{
			ans += bucket;
		}
		
		print_answer(ans);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » UVa Q10137: The Trip

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机