731-F. Video Cards

2021-03-14 23:57:00 +0800 CST Tags: counting-sort, prefix-sum

出處：https://codeforces.com/contest/731/problem/F
提交：https://codeforces.com/contest/731/submission/107165729

問題：給定 $n\in[1,200000]$ 個介於 $[1,200000]$ 的正整數，請問當我們挑任一數字作為基底，並與其他所有不小於該基底的原數字稍稍向下調整為該基底的倍數之後的新數字作加總的最大值。

解法：龜速直觀解法為嘗試每一個基底，接著對其他不小於該基底的數字有向下調整的動作 (truncate) 之後再加總，因為基底總共有 $n$ 個，每次加總的時間複雜度為 $\mathcal O(n)$，很明顯地這樣子最後會得到 $\mathcal O(n^2)$ 是會造成 TLE，本題的考點便在於如何使用 counting sort 和 prefix sum 技巧壓低時間複雜度。標準解法為先行統計 count[i] 為 1 ~ i 的數字個數，接著一樣是嘗試每個基底，但此時與直觀解法不同，我可以很迅速地得到在 truncate 之後是為該基底乘以某個特定倍數的數字個數，舉例來說，假設目前基底為 7，那麼想知道 truncate 之後的值是為 21 的數字個數便可以由 count[27] - count[20] 求得，因為只有 21 ~ 27 這個區間的數字會有這樣的現象。此解法的時間複雜度會是 $\mathcal O(n + m\log_2 m)$，其中 $\mathcal O(n)$ 為預處理，而假設 $m$ 是最大出現的數字，那麼每次嘗試基底 $b$ 的時間為 $\mathcal O(m/b)$，於是乎根據調和級數 $m/1 + m/2 + … + m/m = \mathcal O(m\log_2 m)$。

心得：當我們看到題目有限定數據範圍的時候，就要提高警覺 counting sort 有很高機率會派上用場！

實作：

 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


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

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    int n, m=1, count[200001]={0};
    long long t, ans=0;
    cin >> n; // 所有數字的個數
    for(int i=0; i<n; i++) {
        cin >> t;
        count[t] += 1; // 先記錄每個不同的值各自出現了幾次
        m = max(m, (int)t); // 記錄最大出現過的值是多少，設為之後的上界以增進效率
    }
    for(int i=2; i<=m; i++) // 之後 count[i] 便為所有落在 1 ~ i 範圍內的數字個數
        count[i] += count[i-1];
    for(int i=1; i<=m; i++) {
        if (count[i]-count[i-1] > 0) { // 出現過的數字才能當 base
            t = 0;
            for(int ik=i; ik<=m; ik+=i)
                t += (long long) ik * (count[min(m, ik+i-1)] - count[ik-1]);
            ans = max(ans, t);
        }
    }
    cout << ans << endl;
    return 0;
}

結果： Example image