✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

🌸 目前本专栏已经上线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. 小兰的交错收益序列

问题描述

小兰手里有一个长度为 的整数序列 。

她准备从中挑出一个子序列 ，要求保持原有相对顺序，但不要求连续。

这份子序列的收益定义为：

也就是说，第奇数个被选中的数会加到答案里，第偶数个会减掉。

请你求出 的最大可能值。

子序列允许为空；如果你不选任何数，那么收益视为 。

输入格式

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

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

对于每组测试数据：

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

输出格式

对于每组测试数据，输出一行一个整数，表示最大可能收益。

样例输入

3
4
4 2 5 3
3
-5 -2 -7
5
1 5 2 3 4

样例输出

7
5
7

样例说明

第一组数据可以选择子序列 ，得到 。

数据范围

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

题解

维护两个状态就可以完成转移。

扫描到当前位置时，维护：

• odd：已经选出的子序列长度为奇数时，能够得到的最大收益。
• even：已经选出的子序列长度为偶数时，能够得到的最大收益。

初始时：

• 空子序列长度为偶数，所以 even = 0。
• 还没有办法凑出奇数长度子序列，所以 odd = -inf。

现在处理一个新数 ，有两种选择：

• 不选它，状态保持不变。
• 选它。

更新奇数长度时，它只能接在偶数长度子序列后面，因此：

更新偶数长度时，它只能接在奇数长度子序列后面，因此：

每个数只用一次，所以转移时要先保存旧状态。

最后答案就是 。其中 even 至少是空子序列的 ，因此全负数组也能自然得到答案 。

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

参考代码

• Python

import sys

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


def solve() -> None:
    t = int(input())
    out = []
    neg_inf = -(10 ** 30)

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

        odd = neg_inf
        even = 0

        for x in arr:
            new_odd = max(odd, even + x)
            new_even = max(even, odd - x)
            odd, even = new_odd, new_even

        out.append(str(max(odd, even)))

    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;
        cin >> n;

        long long odd = -(1LL << 60);
        long long even = 0;

        for (int i = 0; i < n; ++i) {
            long long x;
            cin >> x;

            long long newOdd = max(odd, even + x);
            long long newEven = max(even, odd - x);
            odd = newOdd;
            even = newEven;
        }

        cout << max(odd, even) << '\n';
    }
    return 0;
}

• Java

import java.io.*;

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 = n