大厂真题 / 百度

百度 8.13 笔试真题 - 算法岗

本场考试概述

考试时间：2026年8月13日

考试岗位：算法岗

难度评级：中等偏难

考点分析：

第一题：排序 + 同值分组扫描
第二题：贡献法 + 排序不等式
第三题：埃氏筛 + 倍数计数

建议策略：这三道题都不依赖复杂数据结构，关键是改变枚举对象。第一题把无限多个阈值压缩为有限个状态；第二题把“枚举子数组”改写为“统计每个位置的贡献”；第三题把“逐个元素分解质因数”反转为“按质数统计倍数”。

第 1 题：阈值分界总和逼近

题目描述

给定 $n$ 个元素，第 $i$ 个元素包含三个整数属性：判定值 $h_i$、低位值 $l_i$ 与高位值 $r_i$。

你需要选定一个任意整数阈值 $T$，并确定每个元素的最终取值 $v_i$：

若 $h_i<T$，则 $v_i=l_i$；
若 $h_i\ge T$，则 $v_i=r_i$。

记最终总和为

\[V(T)=\sum_{i=1}^{n}v_i.\]

给定目标整数 $S$，求所有整数阈值 $T$ 中 $

V(T)-S

$ 的最小值。

输入描述

第一行输入一个整数 $n$，表示元素个数。

第二行输入一个整数 $S$，表示目标总和。

接下来 $n$ 行，每行输入三个整数 $h_i,l_i,r_i$。

原始回忆材料未给出完整约束；其中代码注释表明 $n$ 可达 $2\times10^5$。因此实现采用 $O(n\log n)$ 排序，并使用 Python 整数保存总和。

输出描述

输出一个整数，表示 $

V(T)-S

$ 的最小值。

样例 1

输入

输出

样例 2

输入

输出

思路分析

虽然 $T$ 可以取任意整数，但 $V(T)$ 只会在阈值越过某个 $h_i$ 时变化。把所有元素按 $h_i$ 升序排列后，可以从“所有元素都取高位值”的状态开始扫描。

当阈值从不大于最小判定值逐渐增大时，判定值为 $h$ 的元素会从高位值切换为低位值。对于元素 $i$，总和的变化量为

\[l_i-r_i.\]

因此只要维护当前总和，每个元素只需处理一次。

需要特别注意：判定值相同的元素必须整组切换后再更新答案。同一个阈值不可能让判定值相同的元素一部分取低位值、另一部分取高位值；如果在组内更新答案，就会引入实际不存在的状态。

正确性证明

将不同的判定值从小到大记为 $x_1,x_2,\ldots,x_k$。

当 $T\le x_1$ 时，所有元素均取高位值，算法检查了这个状态。
当 $x_j<T\le x_{j+1}$ 时，恰好是判定值不超过 $x_j$ 的元素取低位值，其余元素取高位值。算法处理完判定值为 $x_j$ 的整组元素后，当前总和正好等于该状态的 $V(T)$。
当 $T>x_k$ 时，所有元素均取低位值，算法处理最后一组后也会检查这个状态。

所有可能的阈值都属于上述某个区间，而同一区间内 $V(T)$ 不变。因此算法枚举了全部本质不同的总和，取到的最小绝对差就是答案。

Python 代码

import sys


def solve():
    input = sys.stdin.readline
    n = int(input())
    target = int(input())
    items = [tuple(map(int, input().split())) for _ in range(n)]
    items.sort(key=lambda item: item[0])

    # T <= min(h_i) 时，所有元素均取高位值。
    total = sum(high for _, _, high in items)
    answer = abs(total - target)

    i = 0
    while i < n:
        j = i
        current_h = items[i][0]

        # 相同判定值的元素必须同时完成切换。
        while j < n and items[j][0] == current_h:
            _, low, high = items[j]
            total += low - high
            j += 1

        answer = min(answer, abs(total - target))
        i = j

    print(answer)


solve()

复杂度分析

时间复杂度：$O(n\log n)$，主要开销为排序。
空间复杂度：$O(n)$，用于存储全部三元组。

易错点

相同的 $h_i$ 必须分组处理，不能逐个更新答案。
总和及差值应使用 64 位整数；Python 整数可自动扩容。
初始的“全部取高位值”状态也必须检查。

第 2 题：排列子数组和最大化

题目描述

给定整数 $n$，构造一个长度为 $n$ 的排列 $p$。对于该排列的每一个非空连续子数组，计算其元素和，再把所有子数组的元素和相加。

请最大化这个总和，并输出：

最大总和对 $10^9+7$ 取模后的结果；
任意一个达到最大总和的排列。

长度为 $n$ 的排列由 $1,2,\ldots,n$ 各出现一次组成。

输入描述

输入一个整数 $n$。

原始回忆材料未给出完整约束；其中代码注释表明 $n$ 可达 $3\times10^5$。下面的 $O(n\log n)$ 构造适用于这一规模。

输出描述

第一行输出最大总和对 $10^9+7$ 取模后的结果。

第二行输出一个达到最大总和的排列。

样例 1

输入

输出

21
2 3 1

样例 2

输入

输出

1
1

样例 3

输入

输出

54
2 4 3 1

思路分析

直接枚举所有子数组需要 $O(n^2)$ 个区间。换一个求和顺序：先计算每个位置上的数字会被多少个子数组包含。

对于从 $1$ 开始编号的位置 $i$：

左端点可以从 $1,2,\ldots,i$ 中选择，共 $i$ 种；
右端点可以从 $i,i+1,\ldots,n$ 中选择，共 $n-i+1$ 种。

所以位置 $i$ 被包含的次数，也就是它的权重，为

\[w_i=i(n-i+1).\]

总和可改写为

\[\sum_{i=1}^{n}p_iw_i.\]

现在问题变成：如何把 $1$ 到 $n$ 分配给这些位置，使加权和最大。根据排序不等式，最大的数字应放到最大的权重上，次大的数字放到次大的权重上。

一种直接做法是把位置按权重降序排序，然后依次填入 $n,n-1,\ldots,1$。权重相同的位置如何排序都不影响答案，所以最优排列不唯一。

正确性证明

假设两个位置的权重满足 $w_a>w_b$，但放置的数值满足 $p_a<p_b$。交换这两个位置的数值后，总和的变化量为

\[(p_bw_a+p_aw_b)-(p_aw_a+p_bw_b) =(p_b-p_a)(w_a-w_b)>0.\]

因此任何“较大权重配较小数值”的逆序关系都不是最优的。不断消除逆序关系后，权重和数值一定同序排列。算法正是按权重从大到小依次放入从大到小的数值，所以得到最大总和。

Python 代码

MOD = 1_000_000_007


def solve():
    n = int(input())

    positions = list(range(n))
    positions.sort(
        key=lambda index: -((index + 1) * (n - index))
    )

    permutation = [0] * n
    value = n

    for index in positions:
        permutation[index] = value
        value -= 1

    answer = 0
    for index, number in enumerate(permutation):
        weight = (index + 1) * (n - index)
        answer = (answer + number * weight) % MOD

    print(answer)
    print(*permutation)


solve()

复杂度分析

时间复杂度：$O(n\log n)$，用于按位置权重排序。
空间复杂度：$O(n)$。

易错点

“最大”是对真实整数总和而言，不能使用取模后的权重参与排序。
位置从 $0$ 编号时，权重应写成 $(i+1)(n-i)$。
多个最优排列都可能正确，本地输出与样例不同不代表构造错误。

第 3 题：数组公约数改造

题目描述

给定一个长度为 $n$ 的正整数数组 $a$。你可以执行任意次以下操作：

选择一个下标 $i$；
把 $a_i$ 修改为任意正整数。

求至少需要修改多少个元素，才能使整个数组的最大公约数满足

\[\gcd(a_1,a_2,\ldots,a_n)>1.\]

输入描述

第一行输入一个整数 $n$。

第二行输入 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

原始回忆材料未给出完整约束。下面的值域筛实现适用于 $M=\max(a_i)$ 较小、能够开辟 $O(M)$ 计数数组的场景；材料中的复杂度讨论按 $M$ 约为 $10^6$ 的规模展开。若正式题面的 $M$ 显著更大，应改用质因数分解与去重计数，不能直接开值域桶。

输出描述

输出最少修改次数。

样例 1

输入

3
2 4 6

输出

样例 2

输入

3
1 1 1

输出

样例 3

输入

5
6 10 15 7 9

输出

思路分析

如果最终数组的最大公约数 $g>1$，那么 $g$ 至少包含一个质因子 $p$。所有未修改的元素都必须能被 $p$ 整除。

反过来，如果选定某个质数 $p$，保留原数组中所有能被 $p$ 整除的元素，并把其余元素修改为 $p$ 的倍数，就一定能让最终数组的最大公约数大于 $1$。

所以问题等价于：

找到一个质数 $p$，使原数组中能被 $p$ 整除的元素数量最多。

若最多能保留 best 个元素，答案就是

\[n-best.\]

朴素地对每个元素试除分解质因数，最坏情况下开销较大。这里改为按值域统计：

建立频次数组 count[x]；
用埃氏筛枚举每个质数 $p$；
累加 count[p] + count[2p] + count[3p] + ...，得到能被 $p$ 整除的元素数。

若数组全部由 $1$ 构成，没有任何元素能被质数整除，只能修改全部元素。

正确性证明

设某个最优修改方案得到的数组最大公约数为 $g>1$，取 $g$ 的任意质因子 $p$。方案中所有未修改元素原本都能被 $g$ 整除，因此也都能被 $p$ 整除。可见任何方案保留的元素数，都不会超过某个质数的倍数数量。

另一方面，对任意质数 $p$，保留所有原本能被 $p$ 整除的元素，把剩余元素改为 $p$，便能构造出最大公约数至少为 $p$ 的合法数组。因此，对倍数数量最多的质数执行这个构造，可以保留最多元素、修改最少元素。

算法枚举所有质数并统计其倍数数量，故最终输出 $n-best$ 即为最少修改次数。

Python 代码

import sys


def solve():
    input = sys.stdin.readline
    n = int(input())
    numbers = list(map(int, input().split()))

    limit = max(numbers)
    if limit < 2:
        print(n)
        return

    count = [0] * (limit + 1)
    for number in numbers:
        count[number] += 1

    is_composite = bytearray(limit + 1)
    best = 0

    for prime in range(2, limit + 1):
        if is_composite[prime]:
            continue

        divisible_count = 0
        for multiple in range(prime, limit + 1, prime):
            divisible_count += count[multiple]

        best = max(best, divisible_count)

        if prime * prime <= limit:
            for multiple in range(
                prime * prime, limit + 1, prime
            ):
                is_composite[multiple] = 1

    print(n - best)


solve()

复杂度分析

设 $M=\max(a_i)$。

时间复杂度：筛法与质数倍数统计约为 $O(M\log\log M+n)$。
空间复杂度：$O(M)$。

易错点

数字 $1$ 不被任何质数整除；全为 $1$ 时答案是 $n$。
枚举所有整数作公约数没有必要，只需枚举质数。
复杂度主要受最大值 $M$ 影响，而不只是数组长度 $n$。

这篇文章有帮助吗？

| GitHub 留言