🔗刷题网址: bishipass.com

蚂蚁-2026.03.12-算法岗

1. 零点校准计划

问题描述

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

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

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

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

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

输入格式

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

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

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

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

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

输出格式

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

样例输入

23 51 -2 34 100 0 0 -5

样例输出

10

数据范围

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

题解

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

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

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

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

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

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

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

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

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

参考代码

{% tabs %}

import sysdefsolve_one(arr, k):# 方案一：直接把某个数改成 0。    best_one = min(abs(x) for x in arr)if best_one == 0:return0# 方案二：先做一次合并，再把结果调成 0。    best_two = 10**30if len(arr) >= 2:        arr.sort()        l, r = 0, len(arr) - 1while l < r:            s = arr[l] + arr[r]            best_two = min(best_two, abs(s))if s >= 0:                r -= 1else:                l += 1return min(best_one, k + best_two)defmain():    data = list(map(int, sys.stdin.buffer.read().split()))ifnot 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.*;publicclassMain{staticlongsolveOne(long[] arr, long k){// 方案一：直接把某个数改成 0。long one = Long.MAX_VALUE;for (long x : arr) {            one = Math.min(one, Math.abs(x));        }if (one == 0) {return0;        }// 方案二：先做一次合并，再把结果调到 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);    }publicstaticvoidmain(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 = newlong[n];for (int i = 0; i < n; i++) {                arr[i] = fs.nextLong();            }            sb.append(solveOne(arr, k)).append('\n');        }        System.out.print(sb);    }staticclassFastScanner{privatefinal InputStream in;privatefinalbyte[] buf = newbyte[1 << 16];privateint ptr = 0;privateint len = 0;        FastScanner(InputStream is) {            in = is;        }privateintread()throws IOException {if (ptr >= len) {                len = in.read(buf);                ptr = 0;if (len <= 0) {return -1;                }            }return buf[ptr++];        }longnextLong()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;        }intnextInt()throws IOException {return (int) nextLong();        }    }}

#include<bits/stdc++.h>usingnamespacestd;using ll = longlong;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) {return0;    }// 方案二：先合并一次，再做微调。    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);}intmain(){    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';    }return0;}

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 jsonimport sysimport numpy as npNEG = -1e100defsafe_log(arr):# 概率可能出现 0，这里统一转成一个极小值，避免出现 -inf。return np.where(arr > 0, np.log(arr), NEG)defsolve_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]            best = int(np.argmax(cand))            pre[t, j] = best            dp[t, j] = cand[best] + log_b[j, obs[t]]# 从终点回溯整条最优路径。    last = int(np.argmax(dp[m - 1]))    best = float(dp[m - 1, last])    path = [0] * m    path[m - 1] = lastfor t in range(m - 1, 0, -1):        path[t - 1] = int(pre[t, path[t]])return path, round(best, 6)defmain():    s = sys.stdin.read().strip()ifnot s:return    data = json.loads(s)    pi = np.array(data["pi"], dtype=np.float64)    a = np.array(data["A"], dtype=np.float64)    b = np.array(data["B"], dtype=np.float64)    obs_list = data["obs"]    log_pi = safe_log(pi)    log_a = safe_log(a)    log_b = safe_log(b)    paths = []    vals = []for obs in obs_list:        path, val = solve_one(log_pi, log_a, log_b, obs)        paths.append(path)        vals.append(val)    ans = {"paths": paths, "logp": vals}    sys.stdout.write(json.dumps(ans, ensure_ascii=False, separators=(",", ":")))if __name__ == "__main__":    main()

3. 展区分段打分

问题描述

A 先生正在布置一条展览长廊。长廊上依次摆放了  个展品，第  个展品的参数值是 。

现在需要把整条长廊划分成  个连续展区，覆盖全部展品且互不重叠，并且每个展区的长度至少为 。

对于某个展区，先从中删去恰好  个展品，再计算剩余展品的总贡献。设这个展区删除前的长度是 ，那么其中某个展品  的贡献定义为：

问应该怎样划分，才能使所有展区的总贡献最大。

输入格式

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

第二行包含  个空格分隔的整数 ，表示每个展品的参数值。

保证 。

输出格式

输出一个整数，表示最大总贡献值。

样例输入

5 2 1 0 11 3 2 4 5

3 3 1 0 110 20 30

样例输出

800

0

数据范围

• >
• >
• >
• >
• >

题解

这题要分两层看。

第一层是：如果某一段已经固定了左右端点，该段的最优贡献怎么算。

把每个位置先换成一个基础权重：

这样一段长度为  的区间，删掉  个元素后的总贡献就是：

这里有个很容易忽略的地方：

• >
  如果 ，当然是删掉最小的  个权重更划算。
• >
  如果 ，事情反过来了。因为前面乘了一个负数，想让结果尽量大，就应该删掉最大的  个权重。

所以预处理每个区间时，需要根据  的正负，动态维护“该删掉的那  个值之和”。

第二层才是区间划分。

设  表示区间  单独作为一段时的最大贡献。再设  表示前  个位置划成  段后的最大总贡献。

转移时枚举最后一段的起点：

同时要保证最后一段长度至少为 。

这样做虽然看起来朴素，但规模其实刚好能承受。区间贡献预处理是 ，分段动态规划是 。在 、 的范围下，用这套写法可以通过。

参考代码

{% tabs %}

import heapqimport sysNEG = -(10**30)defbuild_val(w, n, k, c):    val = [[0] * (n + 1) for _ in range(n + 1)]if c >= 0:# c 非负时，删掉最小的 k 个权重。for l in range(1, n + 1):            heap = []            keep = 0            tot = 0for r in range(l, n + 1):                x = w[r]                tot += xif len(heap) < k:                    heapq.heappush(heap, -x)                    keep += xelif x < -heap[0]:                    keep += x + heap[0]                    heapq.heapreplace(heap, -x)                ln = r - l + 1if ln >= k:                    val[l][r] = c * ln * ln * (tot - keep)else:# c 为负时，删掉最大的 k 个权重。for l in range(1, n + 1):            heap = []            keep = 0            tot = 0for r in range(l, n + 1):                x = w[r]                tot += xif len(heap) < k:                    heapq.heappush(heap, x)                    keep += xelif x > heap[0]:                    keep += x - heap[0]                    heapq.heapreplace(heap, x)                ln = r - l + 1if ln >= k:                    val[l][r] = c * ln * ln * (tot - keep)return valdefmain():    data = list(map(int, sys.stdin.buffer.read().split()))ifnot data:return    n, m, k, b, c = data[:5]    a = data[5:5 + n]    w = [0] * (n + 1)for i, x in enumerate(a, 1):        d = x - b        w[i] = d * d    val = build_val(w, n, k, c)    pre = [NEG] * (n + 1)    pre[0] = 0for seg in range(1, m + 1):        cur = [NEG] * (n + 1)        left_min = (seg - 1) * kfor r in range(seg * k, n + 1):            best = NEGfor p in range(left_min, r - k + 1):                cand = pre[p] + val[p + 1][r]if cand > best:                    best = cand            cur[r] = best        pre = cur    print(pre[n])if __name__ == "__main__":    main()

import java.io.*;import java.util.*;publicclassMain{staticfinallong NEG = -(1L << 60);publicstaticvoidmain(String[] args)throws Exception {        FastScanner fs = new FastScanner(System.in);int n = fs.nextInt();int m = fs.nextInt();int k = fs.nextInt();long b = fs.nextLong();long c = fs.nextLong();long[] w = newlong[n + 1];for (int i = 1; i <= n; i++) {long x = fs.nextLong();long d = x - b;            w[i] = d * d;        }long[][] val = newlong[n + 1][n + 1];if (c >= 0) {// c 非负时，删掉最小的 k 个权重。for (int l = 1; l <= n; l++) {                PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());long keep = 0;long tot = 0;for (int r = l; r <= n; r++) {long x = w[r];                    tot += x;if (pq.size() < k) {                        pq.offer(x);                        keep += x;                    } elseif (x < pq.peek()) {                        keep += x - pq.poll();                        pq.offer(x);                    }int len = r - l + 1;if (len >= k) {                        val[l][r] = c * 1L * len * len * (tot - keep);                    }                }            }        } else {// c 为负时，删掉最大的 k 个权重。for (int l = 1; l <= n; l++) {                PriorityQueue<Long> pq = new PriorityQueue<>();long keep = 0;long tot = 0;for (int r = l; r <= n; r++) {long x = w[r];                    tot += x;if (pq.size() < k) {                        pq.offer(x);                        keep += x;                    } elseif (x > pq.peek()) {                        keep += x - pq.poll();                        pq.offer(x);                    }int len = r - l + 1;if (len >= k) {                        val[l][r] = c * 1L * len * len * (tot - keep);                    }                }            }        }long[] pre = newlong[n + 1];long[] cur = newlong[n + 1];        Arrays.fill(pre, NEG);        pre[0] = 0;for (int seg = 1; seg <= m; seg++) {            Arrays.fill(cur, NEG);int leftMin = (seg - 1) * k;for (int r = seg * k; r <= n; r++) {long best = NEG;for (int p = leftMin; p <= r - k; p++) {                    best = Math.max(best, pre[p] + val[p + 1][r]);                }                cur[r] = best;            }long[] tmp = pre;            pre = cur;            cur = tmp;        }        System.out.println(pre[n]);    }staticclassFastScanner{privatefinal InputStream in;privatefinalbyte[] buf = newbyte[1 << 16];privateint ptr = 0;privateint len = 0;        FastScanner(InputStream is) {            in = is;        }privateintread()throws IOException {if (ptr >= len) {                len = in.read(buf);                ptr = 0;if (len <= 0) {return -1;                }            }return buf[ptr++];        }longnextLong()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;        }intnextInt()throws IOException {return (int) nextLong();        }    }}

#include<bits/stdc++.h>usingnamespacestd;using ll = longlong;const ll NEG = -(1LL << 60);intmain(){    ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, k;    ll b, c;cin >> n >> m >> k >> b >> c;vector<ll> w(n + 1);for (int i = 1; i <= n; ++i) {        ll x;cin >> x;        ll d = x - b;        w[i] = d * d;    }vector<vector<ll>> val(n + 1, vector<ll>(n + 1, 0));if (c >= 0) {// c 非负时，删掉最小的 k 个权重。for (int l = 1; l <= n; ++l) {            priority_queue<ll> pq;            ll keep = 0;            ll tot = 0;for (int r = l; r <= n; ++r) {                ll x = w[r];                tot += x;if ((int)pq.size() < k) {                    pq.push(x);                    keep += x;                } elseif (x < pq.top()) {                    keep += x - pq.top();                    pq.pop();                    pq.push(x);                }int len = r - l + 1;if (len >= k) {                    val[l][r] = c * 1LL * len * len * (tot - keep);                }            }        }    } else {// c 为负时，删掉最大的 k 个权重。for (int l = 1; l <= n; ++l) {            priority_queue<ll, vector<ll>, greater<ll>> pq;            ll keep = 0;            ll tot = 0;for (int r = l; r <= n; ++r) {                ll x = w[r];                tot += x;if ((int)pq.size() < k) {                    pq.push(x);                    keep += x;                } elseif (x > pq.top()) {                    keep += x - pq.top();                    pq.pop();                    pq.push(x);                }int len = r - l + 1;if (len >= k) {                    val[l][r] = c * 1LL * len * len * (tot - keep);                }            }        }    }vector<ll> pre(n + 1, NEG), cur(n + 1, NEG);    pre[0] = 0;for (int seg = 1; seg <= m; ++seg) {        fill(cur.begin(), cur.end(), NEG);int left_min = (seg - 1) * k;for (int r = seg * k; r <= n; ++r) {            ll best = NEG;for (int p = left_min; p <= r - k; ++p) {                best = max(best, pre[p] + val[p + 1][r]);            }            cur[r] = best;        }        pre.swap(cur);    }cout << pre[n] << '\n';return0;}

✨ 写在最后：

网站最近上线了八股和选额的功能啦。

最近卡片刷题已经全员开放了，八股和选择题都能直接刷。 我自己还挺喜欢这种刷法的，先看题、自己想，再翻面看答案，会比一直往下看题库更有“在准备面试”的感觉一点。 如果你最近也在刷八股，准备面试、可以来bishipass试试看哦。