我的算法书 - Bash's Big Day

题目说：如果选出的数字最大公约数为 1，它们就会打架。我们要选最多的人且不打架。

反过来想：为了让它们不打架，选出的所有数字的最大公约数 $g$ 必须满足 $g > 1$ 。

这等价于：选出的所有数字都必须是某个整数 $x (x > 1)$ 的倍数。

贪心策略我们不需要找出那个具体的最大公约数是多少，我们只需要找到一个因子 $x$ ，使得输入数组中有最多的数是 $x$ 的倍数。

问题就变成了：在 $2$ 到 $100000$ （题目中 $s_i$ 的最大值）之间，哪一个整数 $x$ 能整除输入数组中数量最多的元素？

算法流程

桶记录（Frequency Array）：因为数字范围比较小（ $10^5$ ），我们可以先用一个数组 cnt[] 记录每个力量值出现的次数。比如 cnt[4] = 2 表示力量为 4 的小精灵有 2 只。
枚举因子（暴力枚举的优化）：我们需要枚举所有可能的公共因子 $i$ （从 2 到 $100000$ ）。
统计倍数：对于每一个因子 $i$ ，我们去统计它的倍数 $i, 2i, 3i, \dots$ 在输入数组中一共出现了多少次。即： $\text{Sum}_i = \text{cnt}[i] + \text{cnt}[2i] + \text{cnt}[3i] + \dots$
取最大值：比较所有 $i$ 对应的总数，最大的那个就是答案。

时间复杂度分析（为什么这样做不会超时？）

你可能会担心：外层循环从 2 枚举到 $10^5$ ，内层循环还要枚举倍数，会不会超时？

这里就要用到调和级数的知识了。设 $V$ 为数字的最大值（ $10^5$ ）。

当 $i=2$ 时，内层循环跑 $V/2$ 次。
当 $i=3$ 时，内层循环跑 $V/3$ 次。
…
总运算次数 = $V/2 + V/3 + \dots + V/V = V \times (1/2 + 1/3 + \dots + 1/V)$ 。

这是一个调和级数，其和近似为 $\ln V$ 。所以总复杂度是 $O(V \ln V)$ 。对于 $V=10^5$ ， $V \ln V \approx 10^5 \times 11.5 \approx 1.15 \times 10^6$ ，这在计算机 1 秒钟能处理的 $10^8$ 次运算范围内，非常快。

cpp 代码

cpp

copy

        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

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

const int maxn = 1e5+5;
int cnt[maxn];
int n;

void init(){
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        int t;
        std::cin >> t;
        cnt[t]++;
    }
}


int main (int argc, char *argv[]) {
    init();
    int ans = 1;
    for(int g = 2;g < maxn ;++g ) // g: 1->maxn
    {
        int now_sum = 0;
        for(int i = g ; i < maxn ;i+=g) {
            now_sum += cnt[i];
        }
        ans = max(ans,now_sum);
    }
    std::cout << ans << "\n";

    return 0;
}

haskell 代码

haskell

copy

        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

        import Data.Array

-- 定义最大值，题目中 s_i <= 100000
maxVal :: Int
maxVal = 100000

solve :: [Int] -> Int
solve xs = ans
  where
    -- 1. 构建频率数组 (桶)
    -- accumArray 的参数含义:
    -- (+) : 累积函数 (遇到相同的下标怎么处理？相加)
    -- 0   : 初始值
    -- (1, maxVal) : 数组下标范围
    -- [(x, 1) | x <- xs] : 数据源，把每个输入数字 x 变成 (下标, 增量) 的元组
    counts :: Array Int Int
    counts = accumArray (+) 0 (1, maxVal) [(x, 1) | x <- xs]

    -- 2. 定义计算函数：给定一个公因子 g，计算它的倍数出现次数之和
    -- [g, 2*g .. maxVal] 利用 Haskell 的语法糖生成公差为 g 的数列
    countMultiples g = sum [counts ! k | k <- [g, 2*g .. maxVal]]

    -- 3. 对 2 到 maxVal 之间的所有数计算结果，取最大值
    -- 注意列表推导式 [countMultiples g | g <- [2 .. maxVal]]
    allScores = [countMultiples g | g <- [2 .. maxVal]]
    
    -- 4. 处理边界情况
    -- 如果输入全是 1，allScores 里的值可能全是 0。
    -- 但题目允许至少带走 1 个（不能自己打自己），所以结果至少是 1。
    ans = max 1 (if null allScores then 0 else maximum allScores)

main :: IO ()
main = do
    -- 读取输入
    _ <- getLine -- 忽略第一行 n，因为 Haskell 处理列表不需要知道长度
    content <- getContents
    -- 将剩余输入转换为整数列表
    let nums = map read (words content) :: [Int]
    
    -- 计算并输出
    print (solve nums)

目录

cpp 代码

haskell 代码