✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

蚂蚁-2026.03.12-算法岗

1. 零点校准计划

问题描述

K 小姐在调试一排能量刻度器。第 个刻度器当前的读数是 。

为了让整套设备进入安全模式，至少要让某一个刻度器的读数变成 。系统允许的操作只有两种，而且每种操作至多使用一次：

1. 选择两个不同的位置 ，把第 个刻度器改成 ，这一步的代价固定为 。
2. 选择一个位置 和一个正整数 ，把 增加或减少 ，这一步的代价为 。

两种操作可以只用一种，也可以按任意顺序各用一次。

请计算，让整套设备进入安全模式所需的最小总代价。

输入格式

第一行包含一个整数 ，表示测试数据的组数。

接下来共有 组数据。对于每组数据：

第一行包含两个整数 ，其含义如上所述。

第二行包含 个空格分隔的整数 ，表示每个刻度器当前的读数。

保证所有测试数据中， 的总和不超过 。

输出格式

对于每组数据，输出一行一个整数，表示最小总代价。

样例输入

2
3 5
1 -2 3
4 10
0 0 0 -5

样例输出

1
0

样例	解释说明
样例 1	第一组数据里，直接把第一个读数 调整成 ，总代价是 。第二组数据本来就已经存在读数为 的刻度器，所以答案是 。

数据范围

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

题解

题目的关键其实只有一句话：最终只要让某个数变成 就够了。

先看最直接的做法。把第 个读数单独调成 ，代价就是 。所以不使用合并操作时，最优值显然是 。

再看另一种情况。假设那次固定代价为 的合并操作用在 上，那么第 个位置会先变成 。如果后面再做一次微调，把它改到 ，总代价就是：

于是问题就变成了：在所有二元组里，找一个让 最小。

这个子问题很经典。把数组排序以后，用双指针从两端往中间扫：

• 当前和大于等于 ，说明偏大了，右指针左移。
• 当前和小于 ，说明偏小了，左指针右移。

双指针移动的过程中，会把最接近 的两数和找出来。

所以最终答案就是下面两种方案的较小值：

时间复杂度是 ，其中排序占主要部分。题目保证所有测试数据中， 的总和不超过 ，因此完全可以通过。

参考代码

{% tabs %}

import sys


def solve_one(arr, k):
    # 方案一：直接把某个数改成 0。
    best_one = min(abs(x) for x in arr)
    if best_one == 0:
        return 0
    # 方案二：先做一次合并，再把结果调成 0。
    best_two = 10**30
    if len(arr) >= 2:
        arr.sort()
        l, r = 0, len(arr) - 1
        while l < r:
            s = arr[l] + arr[r]
            best_two = min(best_two, abs(s))
            if s >= 0:
                r -= 1
            else:
                l += 1
    return min(best_one, k + best_two)


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    t = data[0]
    pos = 1
    out = []
    for _ in range(t):
        n = data[pos]
        k = data[pos + 1]
        pos += 2
        arr = data[pos:pos + n]
        pos += n
        out.append(str(solve_one(arr, k)))
    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    main()

import java.io.*;
import java.util.*;

public class Main {
    static long solveOne(long[] arr, long k) {
        // 方案一：直接把某个数改成 0。
        long one = Long.MAX_VALUE;
        for (long x : arr) {
            one = Math.min(one, Math.abs(x));
        }
        if (one == 0) {
            return 0;
        }
        // 方案二：先做一次合并，再把结果调到 0。
        long two = Long.MAX_VALUE / 4;
        if (arr.length >= 2) {
            Arrays.sort(arr);
            int l = 0;
            int r = arr.length - 1;
            while (l < r) {
                long s = arr[l] + arr[r];
                two = Math.min(two, Math.abs(s));
                if (s >= 0) {
                    r--;
                } else {
                    l++;
                }
            }
        }
        return Math.min(one, k + two);
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int t = fs.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int cs = 0; cs < t; cs++) {
            int n = fs.nextInt();
            long k = fs.nextLong();
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = fs.nextLong();
            }
            sb.append(solveOne(arr, k)).append('\n');
        }
        System.out.print(sb);
    }

    static class FastScanner {
        private final InputStream in;
        private final byte[] buf = new byte[1 << 16];
        private int ptr = 0;
        private int len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

        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);
            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            long val = 0;
            while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sign;
        }

        int nextInt() throws IOException {
            return (int) nextLong();
        }
    }
}

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

using ll = long long;

static ll solve_one(vector<ll> a, ll k) {
    // 方案一：直接把某个数调到 0。
    ll one = LLONG_MAX;
    for (ll x : a) {
        one = min(one, llabs(x));
    }
    if (one == 0) {
        return 0;
    }
    // 方案二：先合并一次，再做微调。
    ll two = (ll)4e18;
    if (a.size() >= 2) {
        sort(a.begin(), a.end());
        int l = 0;
        int r = (int)a.size() - 1;
        while (l < r) {
            ll s = a[l] + a[r];
            two = min(two, llabs(s));
            if (s >= 0) {
                --r;
            } else {
                ++l;
            }
        }
    }
    return min(one, k + two);
}

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        ll k;
        cin >> n >> k;
        vector<ll> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        cout << solve_one(a, k) << '\n';
    }
    return 0;
}

{% endtabs %}

2. 信标译码器

问题描述

小柯在整理一套海上信标监测系统。

系统内部会在若干“隐藏状态”之间切换，但外部只能观测到离散化后的信号编号。现在已经给出了：

• 初始状态分布 。
• 状态转移矩阵 。
• 发射概率矩阵 。
• 多条观测序列 obs。

请为每一条观测序列求出：

1. 最有可能的隐藏状态路径。
2. 这条最优路径对应的对数概率。

要求使用 Viterbi 动态规划完成，并且整个计算过程都在对数域中进行。

输入格式

输入为一行合法的 JSON 字符串，格式如下：

{
  "pi": [0.6, 0.4],
  "A": [[0.7, 0.3], [0.4, 0.6]],
  "B": [[0.5, 0.4, 0.1], [0.1, 0.3, 0.6]],
  "obs": [[0, 0]]
}

其中：

• 的长度为状态数 。
• 是一个 的矩阵。
• 是一个 的矩阵，列下标对应观测符号。
• obs 中一共包含 条观测序列，每个观测值的范围是 。

所有概率矩阵的每一行都已经归一化，不需要额外校验。

输出格式

输出一行 JSON：

{
  "paths": [[q11, q12, ...], [q21, ...], ...],
  "logp": [-2.253795, -2.448768, ...]
}

其中：

• paths 表示每条观测序列对应的最优隐藏状态路径。
• logp 表示对应最优路径的对数概率。
• 输出顺序必须与输入里的 obs 顺序保持一致。

样例输入

{"pi":[0.6,0.4],"A":[[0.7,0.3],[0.4,0.6]],"B":[[0.5,0.4,0.1],[0.1,0.3,0.6]],"obs":[[0,0]]}

样例输出

{"paths":[[0,0]],"logp":[-2.253795]}

数据范围

• 
• 
• 
• 
• 所有浮点计算均使用 float64

题解

这题本质上就是标准的 Viterbi。

设 表示处理到第 个观测值、并且当前隐藏状态是 时，能够得到的最大对数概率。因为题目只要求“最优路径”，所以每一步只保留最优前驱，不需要把所有方案都加起来。

状态转移写出来就是：

为了最后能把整条路径还原出来，还需要一个 pre[t][j]，记录这个最优值是从哪个上一状态转移过来的。

题目要求在对数域计算，这样乘法都会变成加法，既方便，也能避免很小概率连乘时的下溢问题。

每条观测序列都独立处理一次即可。最后从末尾状态里挑一个对数概率最大的点，再沿着 pre 数组一路回溯，就能得到完整路径。

时间复杂度是 。题目里 、、，规模非常小，直接照公式实现就够了。

参考代码

{% tabs %}

import json
import sys

import numpy as np


NEG = -1e100


def safe_log(arr):
    # 概率可能出现 0，这里统一转成一个极小值，避免出现 -inf。
    return np.where(arr > 0, np.log(arr), NEG)


def solve_one(log_pi, log_a, log_b, obs):
    n = log_pi.shape[0]
    m = len(obs)
    dp = np.full((m, n), NEG, dtype=np.float64)
    pre = np.zeros((m, n), dtype=np.int64)
    # 初始化第一位。
    dp[0] = log_pi + log_b[:, obs[0]]
    # 逐位转移。
    for t in range(1, m):
        for j in range(n):
            cand = dp[t - 1] + log_a[:, j]