大厂真题 / 阿里巴巴

阿里 5.9 笔试真题 - AI研发岗

本场考试概述

考试时间：2026年5月9日 考试岗位：AI研发岗 难度评级：中等偏难

考点分析：

第一题：贪心 + 数位枚举（难度中等）
第二题：二分答案 + 滑窗贪心匹配（难度困难）
第三题：状压DP（难度中等）

建议策略：

第一题抓住”前缀照抄、当前位减 1、后面全填 9”的贪心结构，线性扫一遍即可
第二题先识别可行性单调性从而二分答案，内层用最小堆按桩位置最早过期优先匹配
第三题看到 $n \leq 16$ 立刻锁定状压 DP，按 mask 升序转移

第一题：最大数位之和

题目描述

给定一个正整数 $x$，在所有严格小于 $x$ 的非负整数中，找到数位之和最大的那个数并输出。如果有多个数位之和相同，输出任意一个即可。

$x$ 以十进制字符串给出，长度可达 $10^5$。

样例

输入

输出

思路分析

第一步：观察最优解的结构

要让数位之和最大，直觉上每一位都尽量大（填 9）。但必须严格小于 $x$，所以至少在某个位置首次比 $x$ 小——这意味着最优解一定形如”前 $i$ 位原样保留、第 $i$ 位减 1、后面全填 9”。

第二步：枚举断点

设 $x$ 的第 $i$ 位数字为 $d_i$，前 $i$ 位数位之和为 $\text{prefix}_i$。在位置 $i$ 处减 1 后，候选答案的数位之和为：

\[\text{prefix}_i + (d_i - 1) + 9 \times (\text{len} - 1 - i)\]

线性扫描所有位置，取最大值对应的断点。注意 $d_i = 0$ 时无法减 1（会变负），跳过。

第三步：重建答案

取到最优断点 $i$ 后，把前 $i$ 位原样保留、第 $i$ 位减 1、之后全部置 9。最后去掉前导零。

题解代码

import sys

input = sys.stdin.readline

def solve(x):
    n = len(x)
    if n == 1:
        return str(int(x) - 1)
    digits = [ord(c) - 48 for c in x]
    prefix = 0
    best_sum = -1
    best_i = -1
    for i in range(n):
        if digits[i] >= 1:
            cur = prefix + (digits[i] - 1) + 9 * (n - 1 - i)
            if cur > best_sum:
                best_sum = cur
                best_i = i
        prefix += digits[i]
    parts = [chr(48 + digits[k]) for k in range(best_i)]
    parts.append(chr(48 + digits[best_i] - 1))
    parts.extend(['9'] * (n - 1 - best_i))
    s = ''.join(parts).lstrip('0')
    return s if s else '0'

T = int(input())
out = []
for _ in range(T):
    out.append(solve(input().strip()))
sys.stdout.write('\n'.join(out))

复杂度分析

时间复杂度：$O(L)$，$L$ 为所有 $x$ 的数位长度总和 空间复杂度：$O(L)$

第二题：充电桩阈值

题目描述

数轴上有 $n$ 个机器人与 $m$ 个充电桩。第 $j$ 个充电桩位于 $c_j$，可同时为至多 $\text{cap}_j$ 个机器人充电。若机器人与被分配充电桩的距离不超过阈值 $E$，则视为可达。求最小阈值 $E$ 使所有机器人都能被分配到某一充电桩且不超过容量限制；无法覆盖全部则输出 $-1$。

样例

输入

输出

2
50

思路分析

第一步：识别单调性

$E$ 越大，每个机器人的可达范围越广，越容易分配。存在一个临界点：$E$ 从某个值开始变得可行，之后都可行——具备单调性，适合二分答案。

第二步：二分框架

二分 $E \in [0, 10^6]$，每次调用 check 函数判定当前 $E$ 是否可行。

第三步：check 函数——滑动窗口 + 贪心

把机器人按位置升序处理。对当前机器人 $r$，可用的桩必须满足 $\lvert c - r \rvert \leq E$，即 $c \in [r - E, r + E]$。

随着 $r$ 增大，可用桩的窗口单调右移。维护一个按位置升序的最小堆作为候选集：

新进入窗口的桩（$c \leq r + E$）push 入堆
过期的桩（$c < r - E$）或容量耗尽的桩从堆顶弹出

贪心策略：每次给当前机器人分配位置最小的可用桩。因为位置最小的桩最先过期（离开窗口），留着只会浪费。

第四步：无解判断

若所有桩容量之和 $< n$，无论 $E$ 多大都输出 $-1$。

题解代码

import sys
import heapq

input = sys.stdin.readline

def feasible(robots, stations, caps_orig, E):
    m = len(stations)
    p = 0
    heap = []
    caps = list(caps_orig)
    for r in robots:
        while p < m and stations[p][0] <= r + E:
            heapq.heappush(heap, (stations[p][0], stations[p][1]))
            p += 1
        while heap:
            c, idx = heap[0]
            if c < r - E or caps[idx] == 0:
                heapq.heappop(heap)
                continue
            break
        if not heap:
            return False
        c, idx = heap[0]
        caps[idx] -= 1
        if caps[idx] == 0:
            heapq.heappop(heap)
    return True

def solve():
    n, m = map(int, input().split())
    robots = list(map(int, input().split()))
    c = list(map(int, input().split()))
    cap = list(map(int, input().split()))
    if sum(cap) < n:
        return -1
    robots.sort()
    stations = sorted([(c[j], j) for j in range(m)])
    lo, hi = 0, 10 ** 6
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(robots, stations, cap, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

T = int(input())
out = []
for _ in range(T):
    out.append(str(solve()))
sys.stdout.write('\n'.join(out))

复杂度分析

时间复杂度：$O((n + m) \log n \log V)$，$V$ 为值域上界 空间复杂度：$O(n + m)$

第三题：游历 n 个城市

题目描述

有 $n$ 个城市（$n \leq 16$），已知从出发点到每个城市的距离 $d_i$，以及城市间的距离矩阵 $a_{ij}$（$-1$ 表示不可达）。从出发点出发依次游历所有城市，每个城市最多去一次，离开出发点后不再回来。求最小总距离；无法游历完则输出 $-1$。

样例

输入

输出

思路分析

第一步：识别问题模型

这是经典的 Hamiltonian Path 问题——从出发点访问所有节点恰好一次，求最短路径。$n \leq 16$ 直接提示状压 DP。

第二步：状态定义

用 $n$ 位二进制整数 mask 表示已访问城市集合。定义 $f[\text{mask}][i]$ = 已访问集合为 mask 且当前停在城市 $i$ 的最小总距离。

第三步：初始化与转移

初始化：第一步必须从出发点直达某城市 $i$，若 $d_i \neq -1$，则 $f[1 \ll i][i] = d_i$

转移：从状态 $(\text{mask}, i)$ 扩展到尚未访问的城市 $j$（要求 $a_{i][j} \neq -1$）：$f[\text{mask}

(1 \ll j)][j] = \min(f[\text{mask}][i] + a_{i][j})$

第四步：枚举顺序

mask 从小到大枚举，保证转移时来源已算好。最终答案为 $\min_i f[2^n - 1][i]$。

题解代码

import sys

input = sys.stdin.readline
INF = float('inf')

def solve():
    n = int(input())
    d = list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(list(map(int, input().split())))

    full = 1 << n
    f = [[INF] * n for _ in range(full)]

    for i in range(n):
        if d[i] != -1:
            f[1 << i][i] = d[i]

    for mask in range(1, full):
        for i in range(n):
            if not (mask >> i) & 1:
                continue
            cur = f[mask][i]
            if cur == INF:
                continue
            for j in range(n):
                if (mask >> j) & 1:
                    continue
                if a[i][j] == -1:
                    continue
                nm = mask | (1 << j)
                cand = cur + a[i][j]
                if cand < f[nm][j]:
                    f[nm][j] = cand

    ans = min(f[full - 1])
    print(-1 if ans == INF else ans)

solve()

复杂度分析

时间复杂度：$O(2^n \cdot n^2)$，$n = 16$ 时约 $1.7 \times 10^7$ 空间复杂度：$O(2^n \cdot n)$

小结

第一题是贪心数位构造，核心观察是”在某位减 1 后面全填 9”一定最优，线性扫描即可
第二题是二分答案经典题，内层 check 用滑动窗口 + 最小堆实现”最早过期优先”贪心
第三题是 Hamiltonian Path 的状压 DP，$n \leq 16$ 是强烈暗示，按 mask 升序转移即可

这篇文章有帮助吗？

| GitHub 留言