2026-03-28 某外卖厂暑期笔试复盘

第一题：三选一使差值最小

题目大意

给定 $N$ 、 $K$ 和两个长度均为 $N$ 的数组 $A$ 、 $B$ ，其中 $N\le22$ ， $K\le N$ ，元素在 $10^9$ 以内。有两个人，初始值均为 0。第 $i$ 天只能三选一：

给 alpha 加上 $A[i]$ ；
给 beta 加上 $B[i]$ ；
两边都不加，跳过这一天。

跳过的天数最多为 $K$ 。求 $N$ 天后 $|\alpha-\beta|$ 的最小值。

我当时的想法

看到 $N\le22$ ，我先想的是状态压缩 DP。但想了一会儿就发现，只给一个状态保留当前差值最小的方案不够：后面可能需要的是当前差值更大的那条路径。

发现这个问题后，我还是没有及时换方向，继续在原来的 DP 上想办法优化暴力。最后想写一个 $3^{22}$ 的暴力兜底，也没写出来。

问题不在于所有 DP 都不能做，而是这个状态没有保留后面决策需要的信息。比如同一阶段有两种差值 $+3$ 和 $-5$ ，当前看 $+3$ 更好，但后面如果加上 5，反而是 $-5$ 能得到 0。只存绝对值最小的那个，就把这条路径丢了。

思路分析

把每天的选择换成对差值的贡献：选 A 是 $+A[i]$ ，选 B 是 $-B[i]$ ，跳过是 0。要找的就是跳过次数不超过 $K$ 时，所有贡献之和离 0 最近的方案。

直接枚举有 $3^{22}\approx3.1\times10^{10}$ 种选择，太多了。把数组拆成两半，每半最多 11 项，各自只有 $3^{11}=177147$ 种选择，这就是折半搜索。

先枚举左右两半，记录每种方案的差值和跳过次数。右半按跳过次数分组，每组的差值排好序。

然后枚举左半方案。假设它的差值是 $s$ 、跳过了 $c$ 天，就可以在右半跳过 $0\sim K-c$ 天的各组里，二分找最接近 $-s$ 的值。二分位置和前一个位置都检查一下，更新最小绝对值。

这里是“最多 $K$ 次”，所以不能只找右半恰好跳过 $K-c$ 次的那一组。枚举组数还要受右半长度限制，避免 $K$ 比半边长度大时越界。

时间复杂度 $O(3^{\lceil N/2\rceil}(K+1)\log 3^{\lceil N/2\rceil})$ ，空间复杂度 $O(3^{\lceil N/2\rceil})$ 。

代码

下面两题的代码都是事后参考实现。第一题保留折半搜索写法；没有留下的考场原码不作还原。

from bisect import bisect_left


def min_diff(N, K, A, B):
    mid = N // 2
    left_items = list(zip(A[:mid], B[:mid]))
    right_items = list(zip(A[mid:], B[mid:]))

    def enum_states(items):
        states = []

        def dfs(i, s, skip):
            if i == len(items):
                states.append((s, skip))
                return
            a, b = items[i]
            dfs(i + 1, s + a, skip)          # 选 alpha
            dfs(i + 1, s - b, skip)          # 选 beta
            dfs(i + 1, s, skip + 1)          # 跳过

        dfs(0, 0, 0)
        return states

    left_states = enum_states(left_items)
    right_states = enum_states(right_items)

    # 右半按 skip 次数分组
    right_by_skip = [[] for _ in range(len(right_items) + 1)]
    for s, c in right_states:
        if c <= K:
            right_by_skip[c].append(s)
    for arr in right_by_skip:
        arr.sort()

    ans = float('inf')

    for s1, c1 in left_states:
        if c1 > K:
            continue

        remain = K - c1
        target = -s1
        # 上界要同时受 remain 和右半元素个数限制，否则 K > len(right_items) 时会越界
        upper = min(remain, len(right_items))

        for c2 in range(upper + 1):
            arr = right_by_skip[c2]
            if not arr:
                continue
            pos = bisect_left(arr, target)
            if pos < len(arr):
                ans = min(ans, abs(s1 + arr[pos]))
            if pos > 0:
                ans = min(ans, abs(s1 + arr[pos - 1]))

    return ans

第二题：端点和与区间最大值

题目大意

给定长度为 $N$ 的正整数数组 $A$ ， $N\le10^5$ ， $A[i]\in[1,10^6]$ 。统计有多少个区间 $[L,R]$ ， $L\le R$ ，满足

A[L]+A[R]>\max(A[L\dots R])

我当时的想法

我先写出了 $O(N^2)$ 暴力。之后想到固定一个点，求它的贡献，但卡在怎么把这个点和区间最大值接起来：只有确定它就是区间最大值，端点的条件才好判断。当时没走通这一步。

思路分析

先数不满足条件的区间，最后用总区间数减掉它们。

因为数组元素都大于 0，只要最大值在端点上，两个端点的和就一定比最大值大。所以不合法区间的最大值只能在内部，且两个端点之和不超过它。

对每个位置 $i$ ，用单调栈找到：

左边第一个严格大于 $A[i]$ 的位置，记为 $p_i$ ，不存在则为 $-1$ ；
右边第一个大于等于 $A[i]$ 的位置，记为 $q_i$ ，不存在则为 $N$ 。

这样，归给 $i$ 的区间不能越过这两个位置。如果区间里有相同的最大值，就归给最右边那个：左边允许相等，右边遇到相等就截断，每个区间只会算一次。

要数的不合法端点就是

L\in[p_i+1,i-1],\quad R\in[i+1,q_i-1],\quad A[L]+A[R]\le A[i]

枚举两侧中较短的一侧。每枚举一个端点 $x$ ，就在另一侧查询有多少个数不超过 $A[i]-A[x]$ 。

关键是这个查询不能每次重新切出整个长区间排序，否则单调数组等情况下仍会退化。可以预先按数组前缀建立持久化线段树：先离散化数值，第 $t$ 棵树记录前 $t$ 个数的频次。两棵前缀树相减，就能在 $O(\log N)$ 时间内查任意下标区间里不超过某个值的数有几个。

为什么只枚举短侧就够快？把每个区间按最大值继续分成左右两部分，就是一棵最大笛卡尔树。某个位置每次被计入短侧，往上对应的子树大小至少翻倍，所以每个位置最多被枚举 $O(\log N)$ 次。总枚举次数 $O(N\log N)$ ，加上每次查询，时间复杂度 $O(N\log^2 N)$ ，空间复杂度 $O(N\log N)$ 。

代码

#include <bits/stdc++.h>
using namespace std;

long long count_pairs(const vector<int>& a) {
    int n = (int)a.size();
    if (n == 0) return 0;

    vector<int> left(n), right(n), st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && a[st.back()] <= a[i]) st.pop_back();
        left[i] = st.empty() ? 0 : st.back() + 1;
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && a[st.back()] < a[i]) st.pop_back();
        right[i] = st.empty() ? n - 1 : st.back() - 1;
        st.push_back(i);
    }

    vector<int> values = a;
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    int m = (int)values.size();

    struct Node {
        int l = 0, r = 0, sum = 0;
    };
    vector<Node> tree(1);  // 0 号是空树
    tree.reserve((size_t)n * 20 + 1);
    vector<int> root(n + 1, 0);

    // 复制一条根到叶子的路径，其他节点与旧版本共用。
    function<int(int, int, int, int)> add =
        [&](int old, int l, int r, int pos) -> int {
            int u = (int)tree.size();
            tree.push_back(tree[old]);
            ++tree[u].sum;
            if (r - l == 1) return u;
            int mid = (l + r) / 2;
            if (pos < mid) {
                int child = add(tree[old].l, l, mid, pos);
                tree[u].l = child;
            } else {
                int child = add(tree[old].r, mid, r, pos);
                tree[u].r = child;
            }
            return u;
        };

    for (int i = 0; i < n; ++i) {
        int pos = lower_bound(values.begin(), values.end(), a[i]) - values.begin();
        root[i + 1] = add(root[i], 0, m, pos);
    }

    // 两个前缀版本相减，统计数值排名在 [0, k) 内的元素个数。
    function<int(int, int, int, int, int)> query =
        [&](int u, int v, int l, int r, int k) -> int {
            if (k <= l) return 0;
            if (r <= k) return tree[u].sum - tree[v].sum;
            int mid = (l + r) / 2;
            return query(tree[u].l, tree[v].l, l, mid, k)
                 + query(tree[u].r, tree[v].r, mid, r, k);
        };

    auto count_le = [&](int l, int r, int limit) -> int {
        int k = upper_bound(values.begin(), values.end(), limit) - values.begin();
        return query(root[r + 1], root[l], 0, m, k);
    };

    long long bad = 0;
    for (int i = 0; i < n; ++i) {
        int l = left[i], r = right[i];
        if (l == i || r == i) continue;
        if (i - l <= r - i) {
            for (int x = l; x < i; ++x)
                bad += count_le(i + 1, r, a[i] - a[x]);
        } else {
            for (int x = i + 1; x <= r; ++x)
                bad += count_le(l, i - 1, a[i] - a[x]);
        }
    }
    return 1LL * n * (n + 1) / 2 - bad;
}

这两题的卡点都在建模。第一题已经发现当前最优会丢信息，却还留在原来的状态上打转；第二题已经想到固定点计贡献，却没有把“这个点是区间最大值”变成明确的范围。先把这一步说清楚，后面的枚举和计数才接得上。

2026-03-28 某外卖厂暑期笔试复盘

2026-03-28 某外卖厂暑期笔试复盘

第一题：三选一使差值最小

题目大意

我当时的想法

思路分析

代码

第二题：端点和与区间最大值

题目大意

我当时的想法

思路分析

代码

Random Posts