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。

範例輸入：

範例輸出：

$10.00
$11.99
$3991.11

提示：

出處：

ACM10137 (管理：nanj0178)

難以敘述的做法, 自己想一下吧

/**********************************************************************************/
/* 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;
}

我要檢舉

#d223#Q10137#The Trip

台長： Morris

您可能對以下文章有興趣

[UVA][遞迴] 12596 - Recursive Texting

[UVA] 11849 - CD

[UVA][模擬] 758 - The Same Game

[ACM-ICPC][Asia - Seoul][Farthest Pair] 4728 - Squares

人氣(1,066) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:d222. Q11127 Triple-Free Binary Strings
此分類上一篇:d751. Q10049-Selfdescribing Sequence

回應(0)