大厂真题 / 阿里巴巴

阿里 4.18 笔试真题 - 算法岗

本场考试概述

考试时间：2026年4月18日 考试岗位：算法岗 难度评级：中等偏难

考点分析：

第一题：排序 + 贪心博弈（难度简单）
第二题：区间合并 + 二分查找（难度中等）
第三题：线段树维护最小前缀和（难度困难）

建议策略：

第一题关键在于发现 Fool 必须取最大值而 Genius 可自由选择的博弈等价于排序后交替取值
第二题需要注意整数坐标上区间合并的判定条件，以及二分查找定位当前位置
第三题是本场难点，需要用线段树动态维护清零前缀序列的最小前缀和，逐步扫描求最优

第一题：这是什么博弈

题目描述

有 n 个食物，每个食物有一个美味值。Fool 和 Genius 交替选取食物，Fool 先手。Fool 每次必须选当前剩余食物中美味值最大的那个，而 Genius 可以自由选择任意一个，目标是最小化 Fool 的总美味值与 Genius 的总美味值之差（即 Fool - Genius）。输出最终的最小差值。

样例

输入

3
2
10 20
4
2 1 5 8
6
1 1 1 1 1 1

输出

10
4
0

思路分析

第一步：观察博弈结构

Fool 每轮必须取当前最大值，这意味着 Fool 的行为是完全确定的。Genius 的目标是最小化差值，即尽量让自己拿到的总和大（或让 Fool 多拿小的）。关键问题是：Genius 的最优策略是什么？

第二步：推导 Genius 的最优策略

将所有食物按美味值从大到小排序。第一轮 Fool 必取排名第 1 的（最大），然后轮到 Genius。Genius 此时如果取排名第 2 的（次大），那么下一轮 Fool 又必须取当前剩余最大的（排名第 3）。如果 Genius 取了排名第 2 以外的食物，比如取了排名第 4 的，那下一轮 Fool 取的仍然是排名第 2 的（因为它还在），Fool 拿的反而更大了。因此 Genius 的最优策略就是每次取当前剩余中的最大值（即排名第 2 的）。

第三步：结论

排序后，Fool 取下标 0, 2, 4, … 位置的食物，Genius 取下标 1, 3, 5, … 位置的食物。答案 = sum(偶数下标) - sum(奇数下标)。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort(reverse=True)
    fool = sum(a[i] for i in range(0, n, 2))
    genius = sum(a[i] for i in range(1, n, 2))
    print(fool - genius)

T = int(input())
for _ in range(T):
    solve()

复杂度分析

时间复杂度：O(n log n)，排序为瓶颈。 空间复杂度：O(n)，存储数组。

第二题：最短就餐距离

题目描述

数轴上有 n 个禁止区间 [l_i, r_i]（整数坐标），你当前位于整数位置 p。找到离 p 最近的不在任何禁止区间内的整数位置 x，输出

x - p

。

样例

输入

输出

0
0
3

思路分析

第一步：处理区间合并

多个禁止区间可能重叠或相邻，需要先进行合并。注意这里是整数坐标，因此区间 [1,3] 和 [4,5] 实际上覆盖了连续整数 1,2,3,4,5，应当合并为 [1,5]。合并条件：排序后若当前区间的左端点 <= 前一个区间的右端点 + 1，则合并。

第二步：判断 p 是否在某个合并后的区间内

对合并后的区间列表，使用二分查找定位 p。具体来说，找到最后一个左端点 <= p 的区间，检查该区间的右端点是否 >= p。如果 p 不在任何禁止区间内，答案为 0。

第三步：计算最近可达点

如果 p 在某个合并后的区间 [L, R] 内，则最近的合法位置要么是 L-1（往左），要么是 R+1（往右）。答案 = min(p - L + 1, R - p + 1)。

题解代码

import sys
input = sys.stdin.readline
from bisect import bisect_right

def solve():
    line = input().split()
    n, p = int(line[0]), int(line[1])
    intervals = []
    for _ in range(n):
        parts = input().split()
        l, r = int(parts[0]), int(parts[1])
        if l > r:
            l, r = r, l
        intervals.append((l, r))
    
    # 按左端点排序后合并
    intervals.sort()
    merged = []
    for l, r in intervals:
        if merged and merged[-1][1] + 1 >= l:
            merged[-1] = (merged[-1][0], max(merged[-1][1], r))
        else:
            merged.append((l, r))
    
    # 二分查找 p 所在区间
    # 找最后一个左端点 <= p 的区间
    lefts = [iv[0] for iv in merged]
    idx = bisect_right(lefts, p) - 1
    
    if idx >= 0 and merged[idx][0] <= p <= merged[idx][1]:
        L, R = merged[idx]
        print(min(p - L + 1, R - p + 1))
    else:
        print(0)

T = int(input())
for _ in range(T):
    solve()

复杂度分析

时间复杂度：O(n log n)，排序为瓶颈，二分查找 O(log n)。 空间复杂度：O(n)，存储区间列表。

第三题：最大权值

题目描述

给定长度为 n 的数组 a[1..n]，以及两个 1 到 n 的排列 b[1..n] 和 c[1..n]。

操作1（得分操作）：选择一个整数 x (1 <= x <= n)，得分为 a[b[1]] + a[b[2]] + … + a[b[x]]，即 b 的前 x 个位置指向的 a 值之和。
操作2（清零操作）：选择一个整数 y (1 <= y <= n)，将 a[c[1]], a[c[2]], …, a[c[y]] 全部置为 0。

两个操作都是可选的（可以不执行），执行顺序任意。求能获得的最大得分。

样例

输入

输出

6
14
0

思路分析

第一步：分析操作顺序

如果先得分再清零，清零不影响已得的分数，所以清零无意义。如果先清零再得分，清零可以把某些负值元素变为 0，从而增加得分。因此有意义的策略只有两种：(1) 只做得分操作；(2) 先清零再得分。我们需要枚举所有可能的 (x, y) 组合找最大值，同时考虑两个操作都不做（得分为 0）。

第二步：形式化问题

设 B(x) = {b[1], b[2], …, b[x]} 为得分集合，C(y) = {c[1], c[2], …, c[y]} 为清零集合。先清零后得分时，得分 = sum of a[i] for i in B(x) but i not in C(y)，即 B 前缀中未被 C 前缀清零的元素之和。

对于固定的 x，score(x, y) = sum(a[b[1..x]]) - sum(a[b[i]] for b[i] in C(y) and i <= x)。

换一种视角：考虑按 b 的顺序逐个加入元素。当加入 b[x] 时，我们维护在 c 排列上的信息，以快速回答”如果选择清零前 y 个，能消掉多少负贡献”。

第三步：线段树维护最小前缀和

核心观察：对于固定的得分前缀 x，考虑清零前缀 y。被清零的元素是 B(x) 和 C(y) 的交集。我们在 c 的位置上建一棵线段树：

对于 c[j] 这个位置，如果 c[j] 在当前 B(x) 中，则该位置的权值为 a[c[j]]（这是被清零掉的值）；否则权值为 0。
清零操作选前 y 个，实际消掉的值 = c 数组前 y 个位置中有权值的那些之和。
我们的得分 = pref_b(x) - (这些被消掉的值中我们不想要的负数贡献)。

更精确地说：设 pref_b(x) = a[b[1]] + … + a[b[x]]。清零前缀 y 之后的得分 = pref_b(x) - sum(a[c[j]] for j <= y and c[j] in B(x))。

我们希望最大化这个得分，即最小化 sum(a[c[j]] for j <= y and c[j] in B(x))，也就是找 c 序列上权值的最小前缀和（可以为负，对应清零了负值元素，增大了得分）。

第四步：算法流程

为 c 的每个位置 j 建线段树，初始权值全为 0。
按 x = 1, 2, …, n 枚举 b 前缀。加入 b[x] 时，找到 b[x] 在 c 中的位置 pos（预处理 c 的逆映射），在线段树的 pos 位置更新权值为 a[b[x]]。
线段树每个节点维护 (sum, minPre)：sum 为区间总和，minPre 为区间的最小前缀和。合并规则：minPre = min(left.minPre, left.sum + right.minPre)。
每步更新后，当前答案 = pref_b(x) - min(0, root.minPre)。取 min(0, …) 是因为我们也可以选择不清零（y=0），此时减去的是 0。
全局答案 = max(0, max over all x of answer(x))，取 max(0, …) 是因为可以两个操作都不做。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = list(map(int, input().split()))
    
    # c_pos[v] = v 在 c 排列中的位置 (0-indexed)
    c_pos = [0] * (n + 1)
    for i in range(n):
        c_pos[c[i]] = i
    
    # 线段树：每个节点存 (sum, min_prefix)
    # 叶节点初始 (0, 0)
    size = 1
    while size < n:
        size <<= 1
    # tree[i] = (sum, min_prefix)
    tree = [[0, 0] for _ in range(2 * size)]
    
    def update(pos, val):
        pos += size  # 映射到叶节点
        tree[pos][0] = val
        tree[pos][1] = val
        pos >>= 1
        while pos >= 1:
            ls, rs = 2 * pos, 2 * pos + 1
            tree[pos][0] = tree[ls][0] + tree[rs][0]
            tree[pos][1] = min(tree[ls][1], tree[ls][0] + tree[rs][1])
            pos >>= 1
    
    ans = 0
    pref_b = 0
    
    for x in range(n):
        val = a[b[x] - 1]  # b 是 1-indexed
        pref_b += val
        pos = c_pos[b[x]]  # b[x] 在 c 中的位置
        update(pos, val)
        # 最小前缀和：root.min_prefix
        min_pre = min(0, tree[1][1])
        cur = pref_b - min_pre
        if cur > ans:
            ans = cur
    
    print(ans)

T = int(input())
for _ in range(T):
    solve()

复杂度分析

时间复杂度：O(n log n)，枚举 n 个 b 前缀，每次线段树单点更新 O(log n)。 空间复杂度：O(n)，线段树大小为 O(n)。

小结

第一题排序贪心博弈，Fool 被迫取最大值意味着排序后奇偶位交替分配，直接求差即可
第二题区间合并 + 二分，注意整数坐标下相邻区间的合并判定条件，以及边界的距离计算
第三题线段树维护最小前缀和，核心思路是将”先清零再得分”转化为在 c 排列上寻找最小前缀和，通过逐步插入 b 前缀元素到线段树中动态维护答案

这篇文章有帮助吗？

| GitHub 留言