大厂真题 / 美团

美团 3.28 笔试真题 - 研发岗

本场考试概述

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

考点分析：

第一题：贪心排序（难度中等）
第二题：序列DP（难度中等）
第三题：分治 + RMQ（难度困难）

建议策略：

第一题贪心思路清晰后代码量很小，快速拿下
第二题序列DP需要仔细定义状态，注意前缀最值优化
第三题分治+短边枚举是竞赛经典技巧，难度较高但套路固定

第一题：风不吹雨

题目描述

给定一个长度为 n 的数组。你有两种操作：

操作一：选择一个元素 x，将其变为 floor(x/2)。全局最多使用 a 次。
操作二：选择一个元素 x，将其变为 x-k。全局最多使用 b 次。

每个位置可以同时使用两种操作。请最小化数组的总和。

样例

输入

1
3 1 1 3
5 1 7

输出

解释：对 7 使用操作一得到 3，对任意元素使用操作二减去 3，总和 = 5 + 1 + 3 - 3 = 6。

思路分析

这道题的关键在于分别理解两种操作的本质。

操作二的本质：固定收益。无论对哪个元素使用操作二，总和都恰好减少 k。所以 b 次操作二带来的总收益恒为 bk，与选择哪个元素无关。这意味着操作二不需要任何策略，直接从总和中扣除 bk 即可。

操作一的本质：可变收益。对元素 x 使用操作一，总和减少 x - floor(x/2) = ceil(x/2)。这个收益取决于 x 的大小——x 越大，收益越高。

两种操作的先后顺序：如果对同一个元素先操作一再操作二，收益 = ceil(x/2) + k；先操作二再操作一，收益 = k + ceil((x-k)/2)。由于 ceil(x/2) >= ceil((x-k)/2)，先操作一更优。但因为操作二的收益固定为 k，不管先后，操作二的总贡献始终是 b*k。而操作一应该在原始值上计算收益——因为我们要最大化操作一的收益，用原始值（更大）算 ceil(x/2) 更大。

贪心策略：

计算每个元素使用操作一的收益 ceil(x/2) = (x+1)//2
对收益降序排序，取前 a 个
总和减去这些收益，再减去 b*k

为什么排序贪心是正确的？ 因为操作一的 a 次使用是独立的——每次操作一只影响一个元素，且收益只取决于该元素的原始值。我们要从 n 个独立的收益中选 a 个最大的，这正是排序贪心的经典场景。

时间复杂度：O(n log n)，瓶颈在排序。 空间复杂度：O(n)。

import sys
input = sys.stdin.readline

def solve():
    n, a, b, k = map(int, input().split())
    arr = list(map(int, input().split()))
    total = sum(arr)
    gains = sorted(((x + 1) // 2 for x in arr), reverse=True)
    total -= sum(gains[:a])
    total -= b * k
    return total

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

第二题：交替子序列

题目描述

给定长度为 n 的数组 a，选择一个子序列 p1 < p2 < … < pm，最大化：

F = a[p1] - a[p2] + a[p3] - a[p4] + …

即奇数位置（第1、3、5…个）取正号，偶数位置（第2、4、6…个）取负号。

样例

输入

2
3
1 2 3
5
-1 2 -3 4 -5

输出

3
14

解释：

样例一：选择子序列 [3]，F = 3。
样例二：选择子序列 [2, -3, 4, -5, 4] 中的 [2, -3, 4, -5, 4]？实际上选 [-1, -3, 4, -5, 4] 并不对。正确选法：选择下标 2,3,4,5 即 [2, -3, 4, -5]，F = 2-(-3)+4-(-5) = 2+3+4+5 = 14。

思路分析

这是一道经典的序列DP问题，核心在于正确定义状态。

状态定义：

odd_i：以元素 a[i] 结尾、且 a[i] 处于子序列的奇数位置（取正号）时的最大 F 值
even_i：以元素 a[i] 结尾、且 a[i] 处于子序列的偶数位置（取负号）时的最大 F 值

状态转移：

对于 odd_i（a[i] 取正号）：

a[i] 可以作为子序列的第一个元素，此时 F = a[i]
a[i] 前面可以接一个偶数位置结尾的子序列，此时 F = (前面最优的 even 值) + a[i]
因此 odd_i = max(a[i], prefix_max_even + a[i])

对于 even_i（a[i] 取负号）：

a[i] 必须前面有一个奇数位置结尾的子序列（不能单独作为偶数位置开始）
even_i = prefix_max_odd - a[i]

为什么用前缀最值优化？ 朴素转移需要遍历 i 之前所有 j，即 odd_i = max(a[i], max_{j<i}(even_j) + a[i])。注意到 max_{j<i}(even_j) 就是一个前缀最大值，可以在遍历过程中维护，将 O(n^2) 优化到 O(n)。

答案：所有 odd_i 和 even_i 中的最大值。子序列可以在任何位置结束——如果最后一个元素在奇数位（正号），取 odd_i；如果在偶数位（负号），取 even_i。

直觉理解：这道题本质上是在数组中选若干对”高-低”差值累加。奇数位选大的值，偶数位选小的值（最好是负数），这样正负号叠加后收益最大。DP 的妙处在于它自动处理了所有可能的子序列长度和位置组合。

时间复杂度：O(n)。 空间复杂度：O(1)，只需维护两个前缀最值变量。

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    NEG_INF = float('-inf')
    prefix_max_odd = NEG_INF
    prefix_max_even = NEG_INF
    ans = 0
    for i in range(n):
        odd_i = a[i] if prefix_max_even == NEG_INF else max(a[i], prefix_max_even + a[i])
        even_i = NEG_INF
        if prefix_max_odd != NEG_INF:
            even_i = prefix_max_odd - a[i]
        prefix_max_odd = max(prefix_max_odd, odd_i)
        prefix_max_even = max(prefix_max_even, even_i)
        if odd_i != NEG_INF:
            ans = max(ans, odd_i)
        if even_i != NEG_INF:
            ans = max(ans, even_i)
    return ans

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

第三题：AK机的区间

题目描述

给定长度为 n 的数组 a，统计满足以下条件的区间 [l, r]（l < r）的个数：

max(a[l], a[l+1], …, a[r]) < a[l] + a[r]

即区间内的最大值严格小于左右端点之和。

样例

输入

5
1 2 3 4 5

输出

解释：所有 C(5,2) = 10 个区间都满足条件。以 [1,5] 为例，max = 5 = a[5]，而 a[1]+a[5] = 1+5 = 6 > 5，满足。

思路分析

暴力枚举所有区间是 O(n^2)，加上区间最大值查询至少 O(n^2 log n)，对于大数据不可行。本题需要利用分治的思想，结合”短边枚举”技巧达到 O(n log^2 n)。

核心观察：对于区间 [l, r]，设 m 是该区间最大值的位置。条件变为 a[m] < a[l] + a[r]，即 a[l] > a[m] - a[r]（或 a[r] > a[m] - a[l]）。

分治框架：

在当前区间 [L, R] 中找到最大值位置 m（用稀疏表 RMQ 预处理，O(1) 查询）
所有 [l, r] 满足 L <= l <= m <= r <= R 的合法对，分为三类：
- l = m 或 r = m：即一个端点恰好是最大值位置。此时条件简化为 a[m] < a[m] + a[另一端]，即 a[另一端] > 0。由于题目中数组元素为正整数，这些对全部合法，共 (m-L) + (R-m) 对
- l < m 且 r > m：最大值 a[m] 夹在 l 和 r 之间，需要 a[l] + a[r] > a[m]
递归处理子区间 [L, m-1] 和 [m+1, R]

短边枚举 + 二分查找：

对于第三类（l < m, r > m），如何高效计数？

取 m 两侧较短的一边进行枚举（设为短边），较长的一边排序后二分
例如左侧 [L, m-1] 较短，则枚举每个 l，条件 a[r] > a[m] - a[l]，在右侧排序数组中二分查找满足条件的 r 的个数
反之若右侧较短，则枚举 r，在左侧排序数组中二分

为什么短边枚举保证复杂度？ 这是一个经典结论：每次选短边枚举，每个元素在所有递归层中被枚举的总次数是 O(log n)。直觉是：一个元素只有在它所在的那一侧是短边时才会被枚举，而每次被枚举后，下一层递归区间至少缩小一半，所以每个元素最多被枚举 O(log n) 次。加上每次枚举时的 O(log n) 二分查找，总复杂度 O(n log^2 n)。

RMQ 预处理：使用稀疏表（Sparse Table），预处理 O(n log n)，查询 O(1)。这是区间最大值的标准工具。预处理 sp[j][i] 表示从位置 i 开始、长度为 2^j 的区间内最大值的下标。查询时将区间拆成两个可重叠的 2^k 长度区间取最大值。

实现细节：

用栈模拟递归避免栈溢出
短边排序的数组在每层递归中重新构建，不影响总复杂度
注意 bisect_right 找的是严格大于 a[m] - a[i] 的位置，对应的元素个数即 len(sorted_arr) - pos

时间复杂度：O(n log^2 n)。 空间复杂度：O(n log n)，稀疏表的空间。

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

def solve():
    n = int(input())
    v = list(map(int, input().split()))
    LOG = [0] * (n + 1)
    for i in range(2, n + 1):
        LOG[i] = LOG[i // 2] + 1
    K = LOG[n] + 1
    sp = [[0] * n for _ in range(K)]
    for i in range(n):
        sp[0][i] = i
    for j in range(1, K):
        for i in range(n - (1 << j) + 1):
            li = sp[j-1][i]
            ri = sp[j-1][i + (1 << (j-1))]
            sp[j][i] = li if v[li] >= v[ri] else ri

    def qmax(l, r):
        k = LOG[r - l + 1]
        li = sp[k][l]
        ri = sp[k][r - (1 << k) + 1]
        return li if v[li] >= v[ri] else ri

    ans = 0
    stack = [(0, n - 1)]
    while stack:
        l, r = stack.pop()
        if l >= r:
            continue
        m = qmax(l, r)
        ans += (m - l) + (r - m)
        if m - l <= r - m:
            rv = sorted(v[m+1:r+1])
            for i in range(l, m):
                pos = bisect_right(rv, v[m] - v[i])
                ans += len(rv) - pos
        else:
            lv = sorted(v[l:m])
            for j in range(m+1, r+1):
                pos = bisect_right(lv, v[m] - v[j])
                ans += len(lv) - pos
        stack.append((l, m - 1))
        stack.append((m + 1, r))
    print(ans)

solve()

小结

第一题贪心排序，关键洞察是操作二的收益固定、操作一的收益与元素大小正相关，排序取前 a 大即可
第二题序列DP，定义奇偶位置两种状态并用前缀最值优化转移，将 O(n^2) 降至 O(n)
第三题分治+RMQ是竞赛经典组合，短边枚举技巧将复杂度控制在 O(n log^2 n)，建议作为高频模板掌握

这篇文章有帮助吗？

| GitHub 留言