752-E. Santa Claus and Tangerines

2021-03-20 15:10:06 +0800 CST Tags: counting-sort

出處：https://codeforces.com/contest/752/problem/E
提交：https://codeforces.com/contest/752/submission/110484470

問題：給定 $n\in[1,10^6]$ 個介於 $[1,10^7]$ 的正整數，我們希望透過有限次的剖半這些正整數使得這些數字分配給 $k\in[1,2\cdot10^9]$ 個人，其中被分配到的最小數字要最大，意即，讓最衰小的人盡量幸運一點。注意到正整數 $i$ 可以被剖半為 $\lfloor i/2\rfloor$ 以及 $i-\lfloor i/2\rfloor$。

解法：
為了增進效率，可以先加總所有數字，如果總和已經小於人數 $k$，意味著無論怎麼平分 (最後只剩下正整數 1) 也無法均分給這 $k$ 個人，直接回傳無解；如果不是上述情況，那麼最差的狀況下也只是最衰小的人被分配到正整數 1 而已，必定是有解的。先理解以下事實，每次要被剖半的正整數，第二大以後的絕對不可能比最大的那個還要好，因此每次剖半我必須選擇最大的那個。那當我們剖半正整數 $i$ 得到新的正整數 $\lfloor i/2\rfloor$(小) 和 $i-\lfloor i/2\rfloor$(大) 之後只可能會發生以下兩種狀況：(*) 比較小的新正整數 $\lfloor i/2\rfloor$ 已經比當前的第 k 名還要小，那更新後的第 k 名要嘛持平要嘛會往後退，而且從現在開始再剖半任何一個新的正整數都不會再讓第 k 名往前進步，因此程序可就此打住，現在的第 k 名已經最好；(**) 比較小的新正整數 $\lfloor i/2\rfloor$ 其實不輸當前的第 k 名，那麼此時新的第 k 名必須往前進一個數字，並繼續剖分新的最大正整數，直到 (*) 發生為止。

這題精華的地方在於實作細節，如果用單純的 array 或者 linked list 結構來維護，每次更新名次的時候都要花上許多時間，因此參考答案採用 counting sort 技巧，每次觀察當前最大正整數的個數，如果現在全部的正整數數量還不滿人數 k，便從中選取盡量多的數字讓總數能盡快地到達 k；如果現在全部的正整數數量早就已經抵達人數 k，此時才要採用上一段所說的，每次只剖分「一個」最大正整數並進行比較的程序。注意到這整個 counting sort array 在任意時刻只要維護第 1 ~ k 名的資訊就好，第 k+1 名以後的資訊完全不會用到。

心得：這題除了剖分的過程中第 k 名的變動規則很有趣之外，魔鬼也藏在實作細節中，從正整數總數還沒抵達 k 到剛抵達 k 的那一刻，第 k 名數值 (也就是欲求答案) 的更新是最不直覺的，要非常小心。而如果每次只剖分一個數字的話也會導致 TLE，必須 follow 上一段「選取盡量多的數字讓總數能盡快地到達 k」的規則才不會超時。

實作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


#include <bits/stdc++.h>
using namespace std;

long long sum; // 只是為了檢查全部數字和是否不小於人數
int n, k, ans, sum2, minN=INT_MAX, maxN, cnt[10000001];

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    cin >> n >> k;
    for (int i=0; i<n; i++) {
        int t; cin >> t;
        sum += t; maxN = max(maxN, t); minN = min(minN, t);
        cnt[t]++;
    }
    if (sum < k) cout << -1; // 數字和小於人數則不夠分，直接回傳 -1
    else {
        for (int i=maxN; i>=1; i--) {
            sum2 += cnt[i]; // 檢查當前累積的數字總數是否已經達到人數
            if (sum2 >= k) { // 如果已經達到人數
                cnt[i] -= sum2 - k; // 把當前這個數字總數削減到第 k 名為最後一名
                ans = i; // 立刻更新第 k 名的所在數值
                n = k; // 立刻更新數字總數為與人數 k 相同
                break;
            } else if (sum2 == n) { // 如果系統輸入給定的數字總數本來就未達 k 人
                break; // 先暫時不更新 ans 並且跳出迴圈
            }
        }
        for (int i=maxN; i>=2;) { // 直接從最大出現的數字開始平分，比較快
            if (cnt[i]) { // 如果有這個數字可以平分
                if (n==k && i/2<ans) break; // 已經知道第 k 名而且平分之後的較小部分嚴格小於第 k 名，則答案不可能再更好，直接跳出
                else {
                    int diff = max(min(cnt[i], k-n), 1); // 看看還差幾個數字才能讓數字總數 n 到達人數門檻 k，如果已經達標，就還是要再切一個數字看看會不會比較好
                    cnt[i] -= diff; // 有 diff 個 i 數被平分
                    cnt[i/2] += diff; // 多出 diff 個 i/2 數
                    cnt[i-i/2] += diff; // 多出 diff 個 i-i/2 數
                    n += diff; // 總共多出 diff 個數
                    if (!ans && n==k) ans = min(i/2, minN); // 如果切完這刀後數字總數 n 剛好達人數 k，那麼第 k 名必落在最小數。要注意到最小數不一定是現在才出現，有可能是很久之前就已經存在的
                    if (n - k == 1) { // 如果數字總數 n 超過人數 k，此時應該只會差 1
                        cnt[ans]--; n--; // 就把超過的部分砍掉，讓數字總數 n 維持在 k
                        while (!cnt[ans]) ans++; // 往上尋找第 k 名 (最後一名) 新的值
                    }
                }
            } else i--; // 如果沒有則往小的數字查詢
        }
        cout << ans; // 就是我們要的第 k 名的數字
    }
    return 0;
}

結果： Example image