✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

阿里系列-2026.04.01-研发岗

三题的处理方式差别比较大。第一题先定最终保留值；第二题把约束改写成带权图；第三题固定位置后做平衡值统计。

题目一：双账本同步的最少轮数

这题不用纠结每一步具体怎么选下标，先看每一对数最终会停在哪里。终态固定后，总操作数只取决于两侧还需要减少多少；顺着这个方向推下去，最优策略就是把每一位都保留到 。

难度：简单

题目二：偏移约束下的编号恢复

每条约束描述的都是两个点之间的相对距离，所以直接建成带权图最顺手。先在每个连通块里跑出相对位移，遇到冲突就说明无解；如果整块没有冲突，再统一平移到合法的正整数区间里。

难度：中等

题目三：作为上中位数的区间次数

这题如果直接枚举区间会比较慢。更自然的切法是固定位置 ，把比 大的数记成 ，把比它小的数记成 。这样一来，上中位数对应的平衡值只会出现两种情况，左右两边分别做一次配对统计就能算出答案。

难度：中等

1. 双账本同步的最少轮数

问题描述

小基 正在给一套双账本仓储系统做上线前联调。系统每天会保留两份独立的库存快照，一份来自主库，一份来自备库。为了验证后续的同步模块是否稳定，她拿到了两份长度都为 的账本：第一份记录为 ，第二份记录为 ，并且所有数都非负。

这套联调工具只有“扣减”指令，不能直接把某一项调大。小基 想知道，最少需要多少轮扣减操作，才能让两份账本在每个位置上都完全一致。

她可以重复执行下面三种操作中的任意一种：

1. 选择一个下标 ，把 减少 。
2. 选择一个下标 ，把 减少 。
3. 选择两个下标 （可以相同，也可以不同），同时把 和 都减少 。

如果某次操作里有元素当前已经是 ，那么这次操作不能执行。

小基 希望经过若干次操作后，使得对每个位置 都满足 。

请计算最少需要多少次操作。

输入格式

第一行输入一个整数 ，表示测试数据组数。

对于每组测试数据：

• 第一行输入一个整数 ，表示数组长度。
• 第二行输入 个整数 。
• 第三行输入 个整数 。

输出格式

对于每组测试数据，输出一个整数，表示最少操作次数。

样例输入

2
3
2 1 3
1 2 1
4
0 2 2 1
1 0 3 1

样例输出

3
2

数据范围

• 
• 
• 
• 单个测试文件中，所有测试数据的 之和不超过

样例	解释说明
样例1 第 1 组	可以先把第一个账本的第 项和第二个账本的第 项一起减，再把第一个账本的第 项和第二个账本的第 项一起减，最后单独把第一个账本的第 项再减一次，总共 次。
样例1 第 2 组	先把 一起减，再把 一起减，就能得到完全相同的两份账本，因此答案是 。

题解

先看固定终态时要花多少步

设最后两份账本在位置 上都变成了 ，那么一定有：

• 。

此时第一份账本总共需要减少：

第二份账本总共需要减少：

操作 3 每做一次，就能同时消耗一次第一份账本的减少机会和一次第二份账本的减少机会。所以：

• 最多可以配对掉 次。
• 剩下的 次只能单独操作。

因此，对这组固定的 来说，最少操作次数就是：

为什么最终一定取到

把上面的式子展开：

也就是说：

这里前半部分已经固定，所以想让答案最小，就必须让 尽量大。

而每个 都独立地满足 ，因此最优选择显然是：

这时：

• 第一份账本还需要减少的总次数是 。
• 第二份账本还需要减少的总次数是 。

最终答案就是：

复杂度分析

每组数据只需要扫一遍数组。

• 时间复杂度：。
• 空间复杂度：，不计输入存储。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()


def solve() -> None:
    t = int(input())
    out = []

    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))

        # sa / sb 分别统计两份账本里“只能单独再减”的总量。
        sa = 0
        sb = 0

        for i in range(n):
            if a[i] > b[i]:
                # 这一位只能继续减少第一份账本。
                sa += a[i] - b[i]
            else:
                # 这一位只能继续减少第二份账本。
                sb += b[i] - a[i]

        out.append(str(max(sa, sb)))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;

        vector<long long> a(n), b(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        for (int i = 0; i < n; ++i) {
            cin >> b[i];
        }

        // sa / sb 分别记录两份账本中无法再和另一边配对的差值总和。
        long long sa = 0;
        long long sb = 0;

        for (int i = 0; i < n; ++i) {
            if (a[i] > b[i]) {
                // 这一位多出来的部分只能从第一份账本里减掉。
                sa += a[i] - b[i];
            } else {
                // 这一位多出来的部分只能从第二份账本里减掉。
                sb += b[i] - a[i];
            }
        }

        cout << max(sa, sb) << '\n';
    }
    return 0;
}

• Java

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    static class FastScanner {
        private final BufferedInputStream in = new BufferedInputStream(System.in);
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        long nextLong() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            long sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            long val = 0;
            while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sign;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder out = new StringBuilder();

        int t = (int) fs.nextLong();
        while (t-- > 0) {
            int n = (int) fs.nextLong();
            long[] a = new long[n];
            long[] b = new long[n];

            for (int i = 0; i < n; ++i) {
                a[i] = fs.nextLong();
            }
            for (int i = 0; i < n; ++i) {
                b[i] = fs.nextLong();
            }

            // sa / sb 分别表示两边剩余的“独占差值”总量。
            long sa = 0;
            long sb = 0;

            for (int i = 0; i < n; ++i) {
                if (a[i] > b[i]) {
                    // 第一份账本在这个位置多出来的值，需要单独统计。
                    sa += a[i] - b[i];
                } else {
                    // 第二份账本在这个位置多出来的值，需要单独统计。
                    sb += b[i] - a[i];
                }
            }

            out.append(Math.max(sa, sb)).append('\n');
        }

        System.out.print(out);
    }
}

2. 偏移约束下的编号恢复

问题描述

小兰 在整理一批旧设备的调试记录。原始编号已经丢失，但她还保留了一组“两个模块编号之差固定”的备注。现在她需要重新恢复这组模块的合法编号方案。

她要构造一个长度为 的正整数数组 ，并满足若干条“两个位置差值固定”的约束。

一共有 条约束。每条约束给出三个整数 ，表示必须满足：

请判断是否存在一个合法数组，使得：

• 所有约束都成立。
• 对所有 ，都有 。

如果存在，输出任意一组合法答案；如果不存在，输出 -1。

输入格式

第一行输入一个整数 ，表示测试数据组数。

对于每组测试数据：

• 第一行输入两个整数 ，分别表示数组长度和约束条数。
• 接下来 行，每行输入三个整数 ，表示约束 。

输出格式

对于每组测试数据：

• 如果存在合法数组，则输出一行 个正整数 。
• 否则输出 -1。

如果有多组合法答案，输出任意一组即可。

样例输入

2
4 3
1 2 2
3 4 0
1 3 1
3 3
1 2 1
2 3 1
1 3 5

样例输出

3 1 2 2
-1

数据范围

• 
• 
• 
• 
• 所有测试数据中， 的总和不超过
• 所有测试数据中， 的总和不超过

样例	解释说明
样例1 第 1 组	取数组 时，三条约束分别对应 、、，全部成立。
样例1 第 2 组	前两条约束可以推出 ，但第三条要求 ，发生矛盾，因此无解。

题解

把约束写成图上的相对位移

约束

可以改写成：

这说明只要知道了 ，就能确定 。因此可以连一条有向边：

• ，边权为 。

同时也可以得到反向关系：

所以再连一条边：

• ，边权为 。

接下来，在每个连通块里任选一个点作为起点，把它的相对值记成 ，然后沿着图把整块的相对位移都推出来。

什么时候会判无解

设当前已经推得某个点 的相对值是 。

若存在一条边 ，边权为 ，那么就必须满足：

如果之前已经给 赋过值，但新推出来的值和旧值不同，那么这些约束彼此矛盾，答案就是 -1。

相对位移没问题后，怎么变成正整数

对于一个连通块里的点，已经求出的只是相对位移。设这个连通块中的最小值和最大值分别是：

如果给整个连通块统一加上一个常数 ，所有差值关系都不会变。

为了让最小值刚好变成 ，最自然的选择是：

此时整块中的最大值会变成：

只要它不超过 ，这个连通块就能合法落在范围内。
如果已经超过了 ，说明这个连通块无论怎么整体平移，都不可能塞进区间 ，答案仍然是 -1。

复杂度分析

每条边最多被访问两次。

• 时间复杂度：。
• 空间复杂度：。

参考代码

• Python

import sys
from collections import deque

input = lambda: sys.stdin.readline().strip()
INF = 10**18


def solve() -> None:
    t = int(input())
    out = []

    for _ in range(t):
        n, m = map(int, input().split())
        g = [[] for _ in range(n)]

        for _ in range(m):
            i, j, k = map(int, input().split())
            i -= 1
            j -= 1

            # a[i] = a[j] + k
            g[j].append((i, k))
            g[i].append((j, -k))

        dis = [None] * n
        ans = [0] * n
        ok = True

        for s in range(n):
            if dis[s] is not None:
                continue

            # 以当前连通块的起点为基准，先把它的相对值定成 0。
            q = deque([s])
            dis[s] = 0
            comp = [s]
            mn = 0
            mx = 0

            while q and ok:
                u = q.popleft()
                du = dis[u]

                for v, w in g[u]:
                    nd = du + w
                    if dis[v] is None:
                        dis[v] = nd
                        q.append(v)
                        comp.append(v)
                        # 维护这个连通块里的最小相对值和最大相对值。
                        if nd < mn:
                            mn = nd
                        if nd > mx:
                            mx = nd
                    elif dis[v] != nd:
                        # 同一个点被推出了两个不同的值，说明约束矛盾。
                        ok = False
                        break

            if not ok:
                break

            # 把整个连通块整体上移，让最小值正好落到 1。
            add = 1 - mn
            if mx + add > INF:
                ok = False
                break

            for u in comp:
                ans[u] = dis[u] + add

        if not ok:
            out.append("-1")
        else:
            out.append(" ".join(map(str, ans)))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

• Cpp

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

using ll = long long;
static const long long LIM = 1000000000000000000LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;

        vector<vector<pair<int, ll>>> g(n);
        for (int e = 0; e < m; ++e) {
            int i, j;
            ll k;
            cin >> i >> j >> k;
            --i;
            --j;

            // a[i] = a[j] + k