✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

美团-2026.03.28-算法岗

01. 小基的折损压缩清单

问题描述

小基 手里有一份长度为 的资源消耗清单，第 项的当前数值为 。

为了把月底报表压到更低，他手里有两类处理机会：

• 压缩处理：选中一项后，把它改成 。
• 抵扣处理：选中一项后，把它改成 。这个结果允许为负数。

每一项至多执行一次压缩处理，至多执行一次抵扣处理，两种处理都做也可以，顺序任选；当然也可以什么都不做。

整份清单中，压缩处理最多只能使用 次，抵扣处理最多只能使用 次。

请你计算，在最优安排下，整份清单所有数值之和最小能变成多少。

输入格式

每个测试文件包含多组测试数据。

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

对于每组测试数据：

• 第一行输入四个整数 。
• 第二行输入 个整数 。

输出格式

对于每组测试数据，输出一行一个整数，表示最小可能的总和。

样例输入

3
3 1 1 3
5 1 7
1 1 1 5
9
1 0 1 10
3

样例输出

6
-1
-7

数据范围

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

题解

先分别计算两种操作各自能带来多少收益。

对某个数 ：

• 压缩处理会把它变成 ，因此带来的收益是 。
• 抵扣处理的收益恒定就是 。

如果同一项两种都做，最佳顺序一定是先压缩再抵扣。因为这样最终值是 ，比先抵扣再压缩更小。

接下来把答案拆成两部分：

• 抵扣处理无论放在哪一项，收益都一样，都是 ，因此总共减少 。
• 压缩处理要挑收益最大的若干项，也就是挑出 最大的 个数。

最终答案为：

把所有 算出来排序，取前 个即可。

时间复杂度是 ，空间复杂度是 。

参考代码

• Python

import sys

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


def solve() -> None:
    t = int(input())
    out = []
    for _ in range(t):
        n, limit_half, limit_sub, k = map(int, input().split())
        arr = list(map(int, input().split()))

        total = sum(arr)
        gains = [((x + 1) // 2) for x in arr]
        gains.sort(reverse=True)

        best_half = sum(gains[:limit_half])
        answer = total - best_half - limit_sub * k
        out.append(str(answer))

    print("\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, limitHalf, limitSub;
        long long k;
        cin >> n >> limitHalf >> limitSub >> k;

        vector<long long> gains;
        gains.reserve(n);
        long long total = 0;

        for (int i = 0; i < n; ++i) {
            long long x;
            cin >> x;
            total += x;
            gains.push_back((x + 1) / 2);
        }

        sort(gains.begin(), gains.end(), greater<long long>());

        long long bestHalf = 0;
        for (int i = 0; i < limitHalf; ++i) {
            bestHalf += gains[i];
        }

        cout << total - bestHalf - 1LL * limitSub * k << '\n';
    }
    return 0;
}

• Java

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

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

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

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

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

            long value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value * 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();
            int limitHalf = (int) fs.nextLong();
            int limitSub = (int) fs.nextLong();
            long k = fs.nextLong();

            long total = 0;
            long[] gains = new long[n];
            for (int i = 0; i < n; ++i) {
                long x = fs.nextLong();
                total += x;
                gains[i] = (x + 1) / 2;
            }

            Arrays.sort(gains);
            long bestHalf = 0;
            for (int i = 0; i < limitHalf; ++i) {
                bestHalf += gains[n - 1 - i];
            }

            long answer = total - bestHalf - (long) limitSub * k;
            out.append(answer).append('\n');
        }

        System.out.print(out);
    }
}

02. 小基的巡检模型异常筛查

问题描述

小基 正在整理一批巡检记录，希望用单类模型把异常样本提前筛出来。

输入中给出了训练集 train、测试集 test，以及待枚举的 gamma_list 和 nu_list。训练集里的每一行最后一个值是标签，其中：

• 0 表示正常样本；
• 1 表示异常样本。

你需要严格按照下面的流程完成建模：

1. 先从 train 中提取全部正常样本，再执行
   train_test_split(test_size=0.25, random_state=42, shuffle=True)，
   得到正常训练集 X_tr 和正常验证集 X_val_norm。
2. 所有异常样本组成 X_val_anom，只参与验证，不参与训练。
3. 只用 X_tr 估计每一维的均值与标准差；若某一维标准差为 0，将其改成 1。
   然后用同一组参数标准化 X_tr、X_val_norm、X_val_anom 和最终的 test。
4. 对每一组 (gamma, nu)，训练
   OneClassSVM(kernel="rbf", gamma=gamma, nu=nu, shrinking=False, tol=1e-4, cache_size=200, max_iter=-1)。
5. 在验证集 X_val = X_val_norm ∪ X_val_anom 上评估：
   • 用 decision_function 的分值计算 AUC；
   • 用阈值 0 计算 F1。
6. 按以下优先级选择最优超参数：
   • AUC 更大优先；
   • F1 更大优先；
   • nu 更小优先；
   • gamma 更小优先。
7. 用整套正常样本 X_tr ∪ X_val_norm 重新估计标准化参数并重训最优模型，再对 test 输出预测标签：
   • 0 表示正常；
   • 1 表示异常。

输入格式

输入只有一行，是一个合法 JSON 对象，字段如下：

{
  "train": [[...], [...], ...],
  "test": [[...], [...], ...],
  "gamma_list": [...],
  "nu_list": [...]
}

其中：

• train 的每一行最后一个值是标签；
• test 只包含特征；
• 所有特征都是实数。

输出格式

输出一个 JSON 整数数组，表示测试集的预测结果。

样例输入

{"train":[[0,0,0],[-0.1,0.1,0],[0.2,-0.2,0],[5,5,1]],"test":[[0.1,0.0],[5,5]],"gamma_list":[0.05,0.2],"nu_list":[0.05,0.1]}

样例输出

[0,1]

数据范围

• 
• 
• 特征维度
• gamma_list 和 nu_list 的长度都至少为

题解

按题面给出的训练、验证和重训顺序逐步实现即可。

容易出错的地方主要有三处。

1. 训练集只来自正常样本

One-Class SVM 的训练阶段只能喂正常样本。

因此第一步必须先从 train 中拆出：

• 全部正常样本；
• 全部异常样本。

正常样本再固定随机种子切成 X_tr 和 X_val_norm；异常样本整体作为 X_val_anom。

2. AUC 要和“异常为正类”的标签方向对齐

decision_function 的分值越大，表示样本越像正常样本。

但本题里标签 1 表示异常，因此在计算 AUC 时，要把“越大越异常”的分值交给 roc_auc_score。做法就是使用 -decision_function。

而计算 F1 时，直接按照阈值 0 做分类即可：

• 分值小于 0，判为异常；
• 否则判为正常。

3. 最终重训时要重新估计标准化参数

前面的标准化参数只允许用 X_tr 计算，这是为了公平比较不同超参数。

选出最优参数以后，最终模型要在全部正常样本上重训，因此标准化的均值和标准差也应该基于整套正常样本重新估计一次。

把这三处细节处理对，整套流程就能稳定跑通。

这题的数据范围不大，重点在于按要求完成数据划分、评分和重训。

参考代码

• Python

import json
import numpy as np
from sklearn.metrics import f1_score, roc_auc_score
from sklearn.model_selection import train_test_split
from sklearn.svm import OneClassSVM


def normalize_by_train(train_x, *others):
    mean = train_x.mean(axis=0)
    std = train_x.std(axis=0)
    std[std == 0] = 1.0

    converted = [((train_x - mean) / std)]
    for arr in others:
        converted.append((arr - mean) / std)
    return converted


def fit_and_score(train_x, val_x, val_y, gamma, nu):
    model = OneClassSVM(
        kernel="rbf",
        gamma=gamma,
        nu=nu,
        shrinking=False,
        tol=1e-4,
        cache_size=200,
        max_iter=-1,
    )
    model.fit(train_x)

    decision = model.decision_function(val_x).ravel()
    pred = (decision < 0).astype(int)
    auc = roc_auc_score(val_y, -decision)
    f1 = f1_score(val_y, pred)
    return auc, f1


def solve() -> None:
    data = json.loads(input())

    train = np.array(data["train"], dtype=float)
    test = np.array(data["test"], dtype=float)
    gamma_list = data["gamma_list"]
    nu_list = data["nu_list"]

    x = train[:, :-1]
    y = train[:, -1].astype(int)

    normal = x[y == 0]
    anomaly = x[y == 1]

    x_tr, x_val_norm = train_test_split(
        normal,
        test_size=0.25,
        random_state=42,
        shuffle=True,
    )

    x_tr_std, x_val_norm_std, x_val_anom_std, _ = normalize_by_train(
        x_tr,
        x_val_norm,
        anomaly,
        test,
    )

    val_x = np.vstack([x_val_norm_std, x_val_anom_std])
    val_y = np.array([0] * len(x_val_norm_std) + [1] * len(x_val_anom_std))

    best_key = None
    best_pair = None
    for gamma in gamma_list:
        for nu in nu_list:
            auc, f1 = fit_and_score(x_tr_std, val_x, val_y, gamma, nu)
            key = (auc, f1, -nu, -gamma)
            if best_key is None or key > best_key:
                best_key = key
                best_pair = (gamma, nu)

    gamma, nu = best_pair
    full_normal_std, test_std = normalize_by_train(normal, test)

    final_model = OneClassSVM(
        kernel="rbf",
        gamma=gamma,
        nu=nu,
        shrinking=False,
        tol=1e-4,
        cache_size=200,
        max_iter=-1,
    )
    final_model.fit(full_normal_std)

    decision = final_model.decision_function(test_std).ravel()
    pred = (decision < 0).astype(int).tolist()
    print(json.dumps(pred, separators=(",", ":")))


if __name__ == "__main__":
    solve()

03. 小柯的双色树养护排班

问题描述

小柯在做一份为期 天的养护计划。她面前有两棵树：

• 红树
• 黑树

第 天她可以做下面三件事中的一件：

• 给红树浇水，使红树高度增加 ；
• 给黑树浇水，使黑树高度增加 ；
• 什么都不做。

其中“什么都不做”最多只能出现 天。

请你安排这 天的选择，使得最终两棵树高度差的绝对值尽可能小，并输出这个最小值。

输入格式

• 第一行输入两个整数 。
• 第二行输入 个整数 。
• 第三行输入 个整数 。

输出格式

输出一个整数，表示最小可能的高度差绝对值。

样例输入

1 1
5
7

样例输出

0

数据范围

• 
• 
• 

题解

n 只有 ，这是典型的 meet-in-the-middle 规模。

把最终目标写成：

那么第 天的三种选择就是：

• 选红树：差值增加
• 选黑树：差值减少
• 跳过：差值不变，同时跳过次数加一

接下来把这 天拆成左右两半。

对于每一半，暴力枚举所有状态，并按“用了多少次跳过”分类保存所有可能的差值。因为每半最多只有 天，所以状态数大约是 ，完全可控。

合并时，若左半用了 skipL 次跳过，得到差值 sumL，那么右半最多还能使用 k-skipL 次跳过。对右半每个合法跳过次数对应的有序差值表，我们二分找到最接近 -sumL 的位置，就能更新：

的最小值。

总复杂度在 量级，可以通过。

参考代码

• Python

import sys
from bisect import bisect_left

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


def build_sums(add_red, add_black):
    m = len(add_red)
    groups = [[] for _ in range(m + 1)]

    def dfs(idx, skipped, total):
        if idx == m:
            groups[skipped].append(total)
            return
        dfs(idx + 1, skipped, total + add_red[idx])
        dfs(idx + 1, skipped, total - add_black[idx])
        dfs(idx + 1, skipped + 1, total)

    dfs(0, 0, 0)
    return groups


def solve() -> None:
    n, k = map(int, input().split())
    add_red = list(map(int, input().split()))
    add_black = list(map(int, input().split()))

    mid = n // 2
    left_groups = build_sums(add_red[:mid], add_black[:mid])
    right_groups = build_sums(add_red[mid:], add_black[mid:])

    for arr in right_groups:
        arr.sort()

    answer = 10 ** 30
    max_right_skip = len(right_groups) - 1

    for skip_left, left_values in enumerate(left_groups):
        if skip_left > k:
            break
        limit = min(k - skip_left, max_right_skip)
        for value in left_values:
            for skip_right in range(limit + 1):
                arr = right_groups[skip_right]
                pos = bisect_left(arr, -value)
                if pos < len(arr):
                    answer = min(answer, abs(value + arr[pos]))
                if pos > 0:
                    answer = min(answer, abs(value + arr[pos - 1]))

    print(answer)


if __name__ == "__main__":
    solve()

• Cpp

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

static vector<vector<long long>> build_sums(const vector<long long>& addRed, const vector<long long>& addBlack) {
    int m = (int)addRed.size();
    vector<vector<long long>> groups(m + 1);

    function<void(int, int, long long)> dfs = [&](int idx, int skipped, long long total) {
        if (idx == m) {
            groups[skipped].p