🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🍠 去哪儿秋招第一场笔试，来啦！！！

🍥 据说去哪儿笔试有挺多套卷子的，大家可以看看这套和你考的那套是否一致

1️⃣ 非常经典的自定义排序问题

2️⃣ 二分答案，题目比较绕，小伙伴们可以直接看样例解释

3️⃣ 动态规划，很多小伙伴留言说不知道怎么做，没思路。这题的话可以根据数据范围来 猜 做法

关于动态规划

动态规划在具体实现的时候可以使用 递推，也可以使用 记忆化搜索。

对于 DP 新手来说，推荐大家可以尝试后者。

1. 记忆化搜索基于 DFS，方便边界处理。

2. 思路更容易理顺，转移更清晰，代码也会相对较短

3. 如果你原本会写暴力 DFS， 那么就更棒了，只需要改一下，你的代码就能从 超时，变成 AC

如果大家感兴趣，我们会专门出一期针对DP小白，来讲解如何写好记忆化搜索，

如果怕记搜卡常，运行的比较慢，别担心，学长这边总结出来一套规律，可以在写好记搜后 无脑 改成递推的形式

让你从此在春秋招笔试中 不再惧怕 动态规划 ！ ！ ！

🧩 01.最小拼图

问题描述

在一个小镇上，K小姐经营着一家独特的拼图店。她的拼图由多个数字组成，每个数字都代表着一种拼图形状。为了吸引更多的顾客，K小姐希望将这些拼图形状以一种特定的顺序排列，使得拼接后的拼图形状在字典序上是最小的。

她希望通过打乱这些数字的顺序，找到一种拼接方式，使得最终形成的字符串是所有可能拼接字符串中最小的。

输入格式

第一行输入一个整数 ，代表拼图形状的数量。
第二行输入 个整数 ，代表拼图形状的数字。

输出格式

在一行上输出 个整数，代表重新排列后的拼图形状。

样例输入1

3
21 -1 1

样例输出1

-1 1 21

样例输入2

3
2 1 21

样例输出2

1 21 2

数据范围

题解

自定义排序，这题是非常经典的题目了

对于任意两个数字 和 ，比较 和 的字典序。如果 ，那么 应该排在 前面。

tips java 和 python 选手有超时的风险

时间复杂度

代表数组长度 ， 代表单个元素的字符串长度

参考代码

• Python

from functools import cmp_to_key

# 自定义比较函数
def compare(x, y):
    # 拼接两个数字的字符串
    if x + y < y + x:
        return -1  # x 应该在 y 前面
    else:
        return 1   # y 应该在 x 前面

def main():
    n = int(input())  # 输入拼图形状的数量
    arr = list(map(str, input().split())) # 输入拼图形状的数字
    # 使用自定义比较函数进行排序
    arr.sort(key=cmp_to_key(compare))
    print(*arr)

if __name__ == "__main__":
    main()

• Java

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    // 自定义比较器
    static class CustomComparator implements Comparator<String> {
        @Override
        public int compare(String x, String y) {
            // 比较拼接后的字符串
            return (x + y).compareTo(y + x);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 输入拼图形状的数量
        String[] arr = new String[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.next();  // 输入拼图形状的数字
        }
        // 使用自定义比较器进行排序
        Arrays.sort(arr, new CustomComparator());
        System.out.println(String.join(" ", arr));  // 输出排序后的结果
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// 自定义比较函数
bool compare(const string &x, const string &y) {
    return x + y < y + x;  // 比较拼接后的字符串
}

int main() {
    int n;
    cin >> n;  // 输入拼图形状的数量
    vector<string> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];  // 输入拼图形状的数字
    }
    // 使用自定义比较函数进行排序
    sort(arr.begin(), arr.end(), compare);
    for (const auto &s : arr) {
        cout << s << " ";  // 输出排序后的结果
    }
    cout << endl;
    return 0;
}

✨ 02.任务贡献值最大化

问题描述

在一个神秘的冒险世界中，K小姐是一位勇敢的探险者，她通过完成各种任务来积累贡献值，以提升自己的冒险等级。每个任务都有其固定的贡献值，而在完成任务时，K小姐还可以使用翻卡来获得额外的奖励，每张翻卡的奖励值是不同的。

为了鼓励用户参与任务，在开始任务之前，还可以进入"挑战"模式，即预先设置自己能够坚持的天数 ，在完成挑战后，可以得到前 张奖励翻倍卡，你可以自由选择翻倍卡的使用顺序，使得每一天的成长值奖励翻倍，第 张翻倍卡可以将任务完成后的成长值奖励乘以 倍。牛牛比较偷懒，他想要找到最少需要坚持的天数，便能够获得至少 点成长值。

K小姐现在面临一个挑战：为了达到 的贡献值，她最小需要的天数 为多少？如果无法达到目标贡献值 ，她希望能够知道这一点，你需要输出

输入格式

第一行输入两个整数 和 ，代表任务总数和要求的贡献值数量。
第二行输入 个整数 代表每个任务的贡献值。
第三行输入 个整数 代表每个任务的翻卡奖励值。

输出格式

在一行输出一个整数，代表最少需要的天数，如果无法达到目标，则直接输出 -1。

样例输入

5 20
2 6 12 20 20
2 1 2 4 2

样例输出

3

说明

K小姐可以选择翻卡三天。在完成任务后她会获得翻卡：

• 在第一张卡片使用面值为 2 的翻卡，获得 金币。
• 在第二个卡片使用面值为 3 的翻卡，获得 金币。
• 在第三个卡片使用面值为 4 的翻卡，获得 金币。

由于 ，因此 K小姐可以达到目标。可以证明更少的卡片无法满足条件。

示例 2

输入：

2 20
1 2
1 2

输出：

-1

说明

在这个例子中，K小姐无法获得 20 个贡献点，因此输出 -1。

数据范围

题解

二分答案

这题其实题意非常绕，这里简化一下：

你需要找到一个最小的下标 ，使得 ，其中 代表前 的任一排列， 同理

那对于当前 ， 要使得 最大化，显然是小的和小的匹配，大的和大的匹配。

尝试二分天数 ，然后判断一下当前所能达到的最大值是否 即可。

二分搜索的时间复杂度为 ，而每次计算贡献值的复杂度为 ，因此总体时间复杂度为 。对于 的情况，这个复杂度是可以接受的。

参考代码

• Python

import sys
from collections import deque

# 主函数
def main():
    n, m = map(int, input().split())  # 输入任务总数和目标贡献值
    a = list(map(int, input().split()))  # 输入每个任务的贡献值
    b = list(map(int, input().split()))  # 输入每个任务的翻卡奖励值

    l, r = 1, n  # 二分搜索的范围

    # 检查在mid天内是否能达到目标贡献值
    def check(mid):
        c = sorted(a[:mid])  # 贡献值排序
        d = sorted(b[:mid])  # 翻卡奖励值排序
        total = sum(c[i] * d[i] for i in range(mid))  # 计算贡献值总和
        return total >= m  # 判断是否达到目标

    while l < r:
        mid = (l + r) // 2  # 计算中间值
        if check(mid):  # 如果能达到目标
            r = mid  # 缩小范围
        else:
            l = mid + 1  # 增加天数

    # 检查最终的天数
    if check(l):
        print(l)  # 输出最小天数
    else:
        print(-1)  # 输出 -1

if __name__ == "__main__":
    main()

• Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();  // 输入任务总数
        long m = scanner.nextLong();  // 输入目标贡献值
        long[] a = new long[(int) n];  // 贡献值数组
        long[] b = new long[(int) n];  // 翻卡奖励值数组

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextLong();  // 输入贡献值
        }
        for (int i = 0; i < n; i++) {
            b[i] = scanner.nextLong();  // 输入翻卡奖励值
        }

        long l = 1, r = n;  // 二分搜索的范围

        // 检查在mid天内是否能达到目标贡献值
        boolean check(long mid) {
            long[] c = Arrays.copyOfRange(a, 0, (int) mid);  // 贡献值
            long[] d = Arrays.copyOfRange(b, 0, (int) mid);  // 翻卡奖励值
            Arrays.sort(c);