【題解】ZeroJudge d223: 10137 – The Trip

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d223
【解題想法】

  • (Line-18) 讀入金額時,先轉成以一分錢為單位。要四捨五入。
  • (Line-23) 計算平均值時,無法整除的部分,表示有 remain 個人需要多付一分錢。
  • (Line-21) 每人支出的金額先排序。
  • (Line-25) 讓支出金額較高的人多付一分錢。
  • (Line-31) 最後的結果除以 2 避免double count,再除以100調回以元為單位。
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    double x;
    while (cin >> n){
        if (n == 0) break;
        int a[n];
        int sum = 0;
        for (int i = 0; i < n; i++){
            cin >> x;
            a[i] = (int)round(x * 100);
            sum += a[i];
        }
        sort(a, a+n);
        int avg = sum / n;
        int remain = sum - avg * n;
        double ans = 0.0;
        for (int i = n-1; i >= n-remain; i--){
            ans += abs(a[i] - avg - 1);
        }
        for (int i = n-remain-1; i >= 0; i--){
            ans += abs(a[i] - avg);
        }
        cout << "$" << fixed << setprecision(2) << ans / 200.0 << "\n";
    }
    return 0;
}

Python code (credit: Amy Chou)

while True:
    n = int(input())
    if n == 0:
        break
    a = []
    Sum = 0
    for i in range(n):
        a.append(int(round(float(input()) * 100)))
        Sum += a[i]
        
    a.sort()
    avg = Sum // n
    remain = Sum - avg * n
    ans = 0.0
    for i in range(n-1, n - remain - 1, -1):
        ans += abs(a[i] - avg - 1)
        
    for i in range(n - remain - 1, -1, -1):
        ans += abs(a[i] - avg)
        
    print(f"${ans / 200.0:.2f}")
分享本文 Share with friends