Student Councils

題目

#

有 \(n\) 個組別，第 \(i\) 個組別有 \(a_i\) 個人。每一個委員會裡面的人的組別互不相同，且一個委員會要有 \(k\) 個人。一個人只能在一個委員會中，但不一定每個人都需要屬於任何一個委員會。請求出能組成多少個委員會。

解題思路

#

有一種想法是一直對於最大的 \(k\) 個組別人數減一，直到沒辦法湊出新的組合為止。然而，答案可以高達 \(2.5 \times 10^{10}\)，這樣是行不通的。當答案範圍很大，而且滿足單調性（如果不能湊出 \(k\) 個委員會，一定不能湊出 \(k + 1\) 個委員會）的時候，就有機會可以對答案二分搜。

對於每一個委員會數量 \(mid\)，因為每一個委員會每一組至多只能有一個人，每一組所做出的最大可能貢獻為 \(min(mid, 組員個數)\)。貢獻人數總和如果大於等於 \(mid \times k\)，則代表有辦法組成 \(mid\) 個委員會。

用對答案二分搜的技巧，時間複雜度優化成 \(O(nlog(ans))\)，其中 \(ans\) 為 \(2.5 \times 10^{10}\)。

常見錯誤

#

• \(r\) 不要開太小也不要開太大。太小會 WA (至少要到 \(2.5 \times 10^{10}\))，太大會超過 long long 範圍。
• 判斷條件（大於等於 / 大於）和 \(l\) / \(r\) 要不要跳過 \(mid\) 要處理好

完整程式碼

#

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int k, n;
    cin >> k >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    long long l = 0, r = 2.5e10;
    while (l < r) {
        long long mid = (l + r + 1) / 2;
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += min(mid, (long long)a[i]);
        }
        if (sum >= (long long)mid * k) {
            l = mid;
        }
        else {
            r = mid - 1;
        }
    }
    cout << l << "\n";
}