大厂真题 / 阿里巴巴

阿里 5.16 笔试真题 - 工程岗

本场考试概述

考试时间：2026年5月16日 考试岗位：工程岗 难度评级：中等偏难

考点分析：

第一题：贪心构造（难度中等）
第二题：0-1 BFS / 图论最短路（难度中等）
第三题：单调栈 + 贡献换元（难度困难）

建议策略：

第一题抓住”最大数放首位一次贡献 $m-1$ 个逆序对”这一性质，贪心阶段结束后用收尾构造一次性补齐剩余
第二题把两种移动建图——传送是 $0$ 权边、向右是 $1$ 权边，双端队列 BFS 即可 $O(n)$ 求最短路
第三题换元把求和顺序调换，用单调栈维护以每个位置为右端点的后缀最小值之和，避免 $O(n^2)$ 枚举

第一题：逆序对构造

题目描述

给定两个整数 $n$ 和 $k$，构造一个长度为 $n$ 的排列（用 $1$ 到 $n$ 各恰好一次），使得排列的逆序对数量恰好等于 $k$。

逆序对定义：选择一对下标 $i < j$，如果 $a_i > a_j$，则算一个逆序对。

每个测试文件包含多组数据，第一行输入 $T$，接下来 $T$ 行每行两个整数 $n, k$。保证 $k \leq \frac{n(n-1)}{2}$，即一定有解。

样例

输入

输出

2 3
1 2
4 1 2 3

思路分析

第一步：观察逆序对的上界

长度为 $n$ 的排列最多有 $\frac{n(n-1)}{2}$ 个逆序对（完全逆序时取得）。题目保证 $k$ 不超过此上界，所以一定有解。

第二步：贪心策略

如果把当前未使用数集中的最大数 $m$ 放在答案的首位，它大于剩余 $m-1$ 个数，一次性贡献 $m-1$ 个逆序对。

所以贪心策略是：只要 $k \geq m-1$，就把 $m$ 放到最前面，然后 $k$ 减去 $m-1$，$m$ 减 1，继续。

第三步：收尾构造

当 $k < m-1$ 时停止贪心。此时剩余可用数是 $1, 2, \ldots, m$，需要在其中再凑出恰好 $k$ 个逆序对。

方法：把 $k+1$ 放在剩余段首位，后接 $1, 2, \ldots, k$，再接 $k+2, k+3, \ldots, m$。其中 $k+1$ 大于紧随其后的 $k$ 个数（$1$ 到 $k$），贡献恰好 $k$ 个逆序对；后面部分递增不再产生新逆序对。

实现要点：每个位置只被写入一次，整体 $O(n)$。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n, k = map(int, input().split())
    result = []
    m = n
    while m > 1 and k >= m - 1:
        result.append(m)
        k -= m - 1
        m -= 1
    # 收尾：在 1..m 中构造恰好 k 个逆序对
    result.append(k + 1)
    for i in range(1, k + 1):
        result.append(i)
    for i in range(k + 2, m + 1):
        result.append(i)
    print(*result)

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

复杂度分析

时间复杂度：$O(n)$，每个位置只被写入一次。 空间复杂度：$O(n)$，存放排列。

第二题：传送门最短路

题目描述

在一条编号为 $1$ 到 $n$ 的路径上，从位置 $i$ 可以进行两种移动：

以代价 $0$ 通过传送门移动到位置 $a_i$
若 $i < n$，以代价 $1$ 向右移动到位置 $i+1$

给定长度为 $n$ 的数组 $a$（其中 $1 \leq a_i \leq n$）。从位置 $1$ 出发，目标到达位置 $n$。求最小总代价。

多组测试数据，第一行 $T$，每组数据第一行 $n$，第二行 $n$ 个整数 $a_i$。

样例

输入

3
5
1 3 3 5 5
4
2 3 4 4
6
1 1 1 1 1 1

输出

2
0
5

思路分析

第一步：建模为图论问题

把每个位置 $i$ 看作图中的一个节点。从节点 $i$ 出发有两条有向边：

传送边：$i \to a_i$，权重 $0$
右移边：$i \to i+1$（$i < n$ 时），权重 $1$

问题转化为从节点 $1$ 到节点 $n$ 的最短路。

第二步：算法选择 —— 0-1 BFS

边权只取 $0$ 或 $1$ 两种值，这正是 0-1 BFS（双端队列 BFS）的经典应用场景：

遇到 $0$ 权边，将目标节点放入队首（保证低代价节点优先处理）
遇到 $1$ 权边，将目标节点放入队尾

这样队列中节点的距离单调不减，效果等价于 Dijkstra，但不需要优先队列，时间复杂度仅 $O(n)$。

第三步：为什么不用普通 BFS？

普通 BFS 适用于所有边权相等的图。这里边权有两种（$0$ 和 $1$），普通 BFS 无法正确处理”免费传送”的边。

实现要点：距离数组初始化为无穷大，只在能松弛时更新并入队。

题解代码

import sys
from collections import deque
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[1] = 0
    dq = deque([1])

    while dq:
        x = dq.popleft()
        # 0 权边：传送到 a[x-1]
        y = a[x - 1]
        if dist[y] > dist[x]:
            dist[y] = dist[x]
            dq.appendleft(y)
        # 1 权边：向右移动
        if x < n:
            z = x + 1
            if dist[z] > dist[x] + 1:
                dist[z] = dist[x] + 1
                dq.append(z)

    print(dist[n])

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

复杂度分析

时间复杂度：$O(n)$，每个节点最多入队出队各一次。 空间复杂度：$O(n)$，距离数组与双端队列。

第三题：子区间最小值和

题目描述

给定一个长度为 $n$ 的整数数组 $a$。对任意子数组区间 $[l, r]$，定义：

\[f(l, r) = \sum_{i=l}^{r} \min(a_l, a_{l+1}, \ldots, a_i)\]

请计算所有子数组的 $f$ 值之和：

\[\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r)\]

结果对 $10^9 + 7$ 取模后输出。多组测试数据。

样例

输入

输出

15
60

思路分析

第一步：暴力分析与瓶颈

直接按 $l, r$ 枚举再求内层前缀最小值之和是 $O(n^3)$（或优化到 $O(n^2)$），对于 $n \leq 2 \times 10^5$ 不可接受。

第二步：贡献换元

记以位置 $i$ 为右端点的所有后缀最小值之和为：

\[\text{cur}(i) = \sum_{l=1}^{i} \min(a_l, a_{l+1}, \ldots, a_i)\]

那么 $f(l, r) = \sum_{i=l}^{r} \min(a_l, \ldots, a_i)$。调换求和顺序后发现：对于固定的右端点 $i$，外层 $r$ 可取 $i, i+1, \ldots, n$，共 $n - i + 1$ 个值（因为 $r \geq i$ 时 $f(l, r)$ 都包含这一项）。

所以答案为：

\[\text{ans} = \sum_{i=1}^{n} \text{cur}(i) \times (n - i + 1)\]

问题转化为：如何线性维护 $\text{cur}(i)$？

第三步：单调栈维护

从左到右扫描 $i$，维护一个单调递增栈。栈中元素 $(v, c)$ 表示”有连续 $c$ 个左端点的后缀最小值等于 $v$”。

处理位置 $i$ 时，初始化计数 $\text{cnt} = 1$（对应左端点 $l = i$ 本身）。依次弹出栈顶中 $v \geq a_i$ 的元素——这些左端点的后缀扩展到 $i$ 后，最小值被压低为 $a_i$：

\[\text{cur} -= v \times c, \quad \text{cnt} += c\]

弹栈结束后，将 $(a_i, \text{cnt})$ 入栈，并更新：

\[\text{cur} += a_i \times \text{cnt}\]

此时 $\text{cur}$ 即为 $\text{cur}(i)$，乘以 $(n - i + 1)$ 累加到答案中。

关键理解：每个元素至多入栈、出栈各一次，所以总时间是 $O(n)$。

题解代码

import sys
input = sys.stdin.readline

MOD = 10**9 + 7

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    stack = []  # (value, count)
    cur = 0
    ans = 0

    for i in range(n):
        x = a[i]
        cnt = 1
        while stack and stack[-1][0] >= x:
            v, c = stack.pop()
            cur -= v * c
            cnt += c
        stack.append((x, cnt))
        cur += x * cnt
        # 外层 r 可取 i..n-1，共 n-i 个值（0-indexed 下为 n-i）
        ans = (ans + cur % MOD * ((n - i) % MOD)) % MOD

    print((ans % MOD + MOD) % MOD)

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

复杂度分析

时间复杂度：$O(n)$，每个元素至多入栈、出栈各一次。 空间复杂度：$O(n)$，单调栈最大长度为 $n$。

小结

第一题（逆序对构造）：贪心放最大数到首位贡献最多逆序对，剩余部分用一次性收尾构造补齐——构造题的经典套路是”先贪心到不能贪，再精确补齐”
第二题（传送门最短路）：将位置移动建模为图，$0$ 权传送边 + $1$ 权右移边，双端队列 BFS（0-1 BFS）$O(n)$ 解决——遇到边权只有 $0/1$ 两种的最短路问题，第一时间想到 0-1 BFS
第三题（子区间最小值和）：通过交换求和顺序将三重循环降为一重，再用单调栈动态维护以每个位置为右端点的后缀最小值之和——单调栈 + 贡献换元是处理”所有子区间的 min/max 相关求和”的标准武器

这篇文章有帮助吗？

| GitHub 留言