2011-09-18 08:40:26Morris
d223. Q10137 The Trip
d223. Q10137 The Trip
內容 ：
Q10137: The Trip
有一群學生組成一個社團，他們每年都會到國外去旅遊。過去幾年他們已經去過Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, 和 Atlanta。今年春天他們計畫到Eindhoven。
學 生們都同意旅遊所花的錢應該要平均分攤，但是實際上在付錢的時候卻不太方便。所以有人先付車錢，有人付餐費，有人付門票費用。等到旅遊結束後，每個人統計 自己出了多少錢，然後出的比較少的人必須拿錢給出的比較多的人，使得每個人所出的錢都相等，如果無法每個人出的錢相等，最多只能相差一分錢（美金的一分 錢，one cent）。你現在的任務就是：給你每個學生旅遊時出的錢，請你算出最少有多少錢要交換（就是出的少的人拿錢給出的多的人），使得每個人所出的錢都盡可能 接近。
輸入說明
：
輸入含有多組測試資料。
每組測試資料的第一列有1個整數 n，代表學生的人數。接下來的 n 列為每個學生旅遊時出的錢，最小單位為一分錢。學生最多不會超過1000人，每個人出的錢不會超過美金$10,000.00元。
n=0代表輸入結束，請參考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
提示
：
出處
：
/**********************************************************************************/
/* Problem: d223 "Q10137 The Trip" from ACM10137 */
/* Language: C (589 Bytes) */
/* Result: AC(0ms, 236KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-18 08:31:02 */
/**********************************************************************************/
#include<stdio.h>
main() {
int n, A[1000], x, y, i, j;
while(scanf("%d", &n) == 1 && n) {
int sum = 0;
for(i = 0; i < n; i++) {
scanf("%d.%d", &x, &y);
A[i] = x*100+y, sum += A[i];
}
int ave = sum/n, tmp = 0;
int t1 = 0, t2 = 0;
for(i = 0; i < n; i++)
if(A[i] < ave) {
t1 += ave - A[i];
A[i] = ave;
}
t2 = t1;
for(i = 0; i < n; i++)
if(A[i] > ave) {
t2 -= A[i] - ave;
A[i] = ave;
tmp ++;
}
if(t2 < 0) {
if(-t2 > tmp)
t1 += -(t2+tmp);
}
printf("$%d.%02d\n", t1/100, t1%100);
}
return 0;
}