d223: 10137 - The Trip

2021-07-04 21:43:06 +0800 CST Tags: math

出處：https://zerojudge.tw/ShowProblem?problemid=d223
提交：https://zerojudge.tw/Submissions?problemid=d223&account=allllllan123456

問題：給定不超過 1000 位學生旅遊時各自先墊出的旅費，而且都不超過 1000000 元。為了公平，旅遊結束後旅費必須被平分，如果無法平分，則希望能以最少的金錢量交換使得每個人最後所出的旅費最多只能相差 1 元，請問最少必須交換多少元才能盡量達到公平？

解法：首先根據總額能算出平分之後的上界 aveH 與下界 aveL，接著就能得到平分之前每個人超出 aveH 的總額度 diffH 與低於 aveL 的總額度 diffL，為了確保每個人平分之後的旅費都會介於 aveL 和 aveH 之間，那麼至少有 diffH 的冗餘額度要被挪去填補其他漏洞，也至少有 diffL 額度的漏洞必須被填補起來，由此可見至少須交換 max(diffL, diffH) 元之後冗餘額度和漏洞方不復存在。注意到當 diffH $>$ diffL，那麼填補完漏洞後剩下的冗餘額度 diffH $-$ diffL 就算全部拿去墊高那些已經達到基本門檻 aveL 的旅費，仍然能確保至少有一個人的旅費維持在基本門檻 aveL，否則就違反了 aveL 的定義；當 diffH $<$ diffL，那麼拿 diffH 連帶那些本來就已經在上界 aveH 的旅費一起填補完漏洞之後，仍能確保至少有一個人的旅費維持在上界 aveH，否則就違反了 aveH 的定義；因此 max(diffL, diffH) 必然是一個可行的答案。

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
 5    int n, arr[1000];
 6    while (cin >> n && n) {
 7        char ch; int a, b, sum=0;
 8        for (int i=0; i<n; i++)
 9            cin >> a >> ch >> b, arr[i] = a*100 + b, sum += arr[i];
10        int diffL=0, diffH=0, aveL=sum/n, aveH=aveL+(sum%n>0);
11        for (int i=0; i<n; i++)
12            if (arr[i] >= aveH) diffH += arr[i] - aveH;
13            else diffL += aveL - arr[i];
14        int ans = max(diffL, diffH);
15        cout << '$' << ans/100 << '.' << setfill('0') << setw(2) << ans%100 << '\n';
16    }
17    return 0;
18}