题目大意：n个学生去旅行，旅行中每个学生先垫付，最后平摊所有费用，多退少补，并且支出差距控制在1分钱以内，求最小的交易金额。
@2013-8-16
以前在zoj做过，把原来的代码直接提交了，虽然AC了，可是记得原来有问题，再一看确实感觉有问题，竟然AC了...然后就自己重写，写完之后总是WA，就放下了，过一段时间在看，再改，提交，仍是WA，太打击人了，不算难的一道题把我虐成这样...今天看World of Seven上的解法时猛然醒悟，自己一直在纠结精度方面的问题，却没发现在向下截取aver时转换成int后直接除100，变成了整数的除法了...只能无语了...
自己的思路就是求平均数后向下截取，然后用 总金额-平均数*n 得到少的金额，对每人的花费进行排序，少的金额就通过让后面的人多拿一美分补上。
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1010 int cmp(const void *_a, const void *_b)
{
double *a = (double*)_a;
double *b = (double*)_b;
return *a - *b;
} int main(void)
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int n, i, p;
double aver, sum, exchange;
double cost[MAXN];
while (scanf("%d", &n) != EOF)
{
if (n == ) break;
sum = ;
for (i = ; i < n; i++)
{
scanf("%lf", &cost[i]);
sum += cost[i];
}
aver = sum / n;
aver = (int)(aver*)/100.0; /* floor the aver */
exchange = ;
p = (int)((sum-aver*n)/0.01+0.1);
qsort(cost, n, sizeof(double), cmp);
for (i = n-; i >= n-p; i--)
if (cost[i] > aver+0.01)
exchange += cost[i]-(aver+0.01);
for (i = n-p-; i >= ; i--)
if (cost[i] > aver)
exchange += cost[i]-aver;
printf("$%.2lf\n", exchange);
}
return ;
}
这个题原来留了好几份代码，现在看看也能看出一些东西，从最初的用c自己用选择排序进行排序到后来用qsort函数排序，到现在用c++的sort，以及代码风格的一些小小改进，发现自己也不是毫无变化了：D，不过长进的也就这些罢了，算法方面还是没什么长进 -_-||
网上流行另一个版本，World of Seven 上如下描述：
The problem with this problem may be related to precision error. Here is solution by Neilor:
double highx = (int)((total/n+0.0099)*100);
double lowx = (int)((total/n)*100);
highx /= 100;
lowx /= 100;
Where total is the total sum of the money and n is the number of students.
Then, test each student money if is > than highx or < than lowx, accumulate
(student[i]-highx) or (lowx-students[i]), respectively.
Then, output the variable that have the bigger value.
不理解为什么可以这样做，也许某天就顿悟了呢？：D