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

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

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

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

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

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

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

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

🌈 携程秋招笔试，来啦！！！

🍥 这次笔试倒反天罡，粉丝反馈，感觉第一题倒是四题中最难调和写的，调了很久才过, 本次四题都包含了贪心的思路，名副其实的 贪心场！

1️⃣ 小学数学题，贪心+推公式

2️⃣ 排序+贪心，题目描述看起来很吓人，分析完之后不难

3️⃣ 二分答案的题目，需要分析出单调性质, check的时候可以贪心

4️⃣ 排序+贪心，需要分析出题目的性质，这点比较困难

🎁 01.LYA的宝藏探险 评测链接🔗

问题描述

LYA是一位热爱冒险的探险家。她最近发现了一个神秘的遗迹，这个遗迹是一个 的网格地图。地图的左上角坐标为 ，右下角坐标为 。每个格子 都藏有一件宝物，其价值为 。

LYA从左上角 开始她的探险。每一步，她可以选择向上、下、左、右四个方向中的一个移动到相邻的格子。每到达一个格子，LYA就能获得该格子中的宝物。

有趣的是，这个遗迹似乎有某种神奇的力量。当LYA离开一个格子后，该格子的宝物会立即重新出现，仿佛从未被取走过。

然而，LYA的探险时间有限。她最多只能移动 步。

现在，LYA想知道在有限的步数内，她最多能获得多少价值的宝物？

输入格式

第一行输入一个整数 ，表示询问的次数。

接下来 行，每行输入三个整数 ，分别表示地图的行数、列数和LYA最多可以移动的步数。

输出格式

输出 行，每行一个整数，表示对应询问中LYA能获得的最大宝物价值。

样例输入

1
2 2 5

样例输出

12

数据范围

题解

思维+推公式

来看看格子的价值分布。格子 的价值是 。这意味着随着 的增加，价值增加得更快（每次增加 ），而 的增加则相对缓慢（每次只增加 1）。

2. 基于这个观察，可以得出一个重要结论：在大多数情况下，向下移动比向右移动更有价值。

3. 那么，最优策略是什么呢？它分为几个阶段：

   • 首先，尽可能地向下移动，直到到达最后一行。
   • 然后，向右移动到最右边的列。
   • 如果还有剩余步数，就在最后一行来回移动（因为最后一行的价值最高）。

4. 但是，如果 （即只有一列），那么在最后一列上下移动会比在最后一行左右移动更有价值。

参考代码

• Cpp

#include <iostream>
using namespace std;
typedef long long LL;

void calculateMaxValue() {
    int n, m, k;
    cin >> n >> m >> k;
    LL ans = 0;

    // 处理垂直移动
    if (k >= n - 1) {
        k -= n - 1;
        ans += 1LL * (n - 1) * m * n / 2;
    } else {
        ans += 1LL * k * m * (k + 1) / 2;
        k = 0;
    }

    // 处理水平移动
    int lastRow = (n - 1) * m;
    if (k >= m - 1) {
        ans += 1LL * (lastRow + 1 + lastRow + m - 1) * (m - 1) / 2;
        k -= m - 1;
    } else {
        ans += 1LL * (lastRow + 1 + lastRow + k) * k / 2;
        k = 0;
    }

    // 处理剩余步数
    int maxVal = n * m - 1;
    int secondMax = maxVal - 1;
    if (k > 0) {
        ans += 1LL * (k + 1) / 2 * secondMax;
        ans += 1LL * k / 2 * maxVal;
    }

    cout << ans << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        calculateMaxValue();
    }
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static void calculateMaxValue(Scanner scanner) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        long ans = 0;

        // 处理垂直移动
        if (k >= n - 1) {
            k -= n - 1;
            ans += (long)(n - 1) * m * n / 2;
        } else {
            ans += (long)k * m * (k + 1) / 2;
            k = 0;
        }

        // 处理水平移动
        int lastRow = (n - 1) * m;
        if (k >= m - 1) {
            ans += (long)(lastRow + 1 + lastRow + m - 1) * (m - 1) / 2;
            k -= m - 1;
        } else {
            ans += (long)(lastRow + 1 + lastRow + k) * k / 2;
            k = 0;
        }

        // 处理剩余步数
        int maxVal = n * m - 1;
        int secondMax = maxVal - 1;
        if (k > 0) {
            ans += (long)(k + 1) / 2 * secondMax;
            ans += (long)k / 2 * maxVal;
        }

        System.out.println(ans);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            calculateMaxValue(scanner);
        }
        scanner.close();
    }
}

• Python

def calculate_max_value():
    n, m, k = map(int, input().split())
    ans = 0

    # 处理垂直移动
    if k >= n - 1:
        k -= n - 1
        ans += (n - 1) * m * n // 2
    else:
        ans += k * m * (k + 1) // 2
        k = 0

    # 处理水平移动
    last_row = (n - 1) * m
    if k >= m - 1:
        ans += (last_row + 1 + last_row + m - 1) * (m - 1) // 2
        k -= m - 1
    else:
        ans += (last_row + 1 + last_row + k) * k // 2
        k = 0

    # 处理剩余步数
    max_val = n * m - 1
    second_max = max_val - 1
    if k > 0:
        ans += (k + 1) // 2 * second_max
        ans += k // 2 * max_val

    print(ans)

t = int(input())
for _ in range(t):
    calculate_max_value()

📚 02.图书馆整理员 评测链接🔗

问题描述

K小姐是一位图书馆整理员。她最近接到了一项特殊任务：整理一批新到的图书。这批图书共有 本，每本书都有一个独特的编号。

K小姐的任务是按照以下规则整理这些书：

1. 每次她可以从书架上选择 本书。
2. 这 本书中，编号最大和最小的差值不能超过 。
3. 从这 本书中，她需要将编号最小的那本书永久移出书架。
4. 其余的书则放回书架。

K小姐可以重复这个过程，直到无法找到符合条件的 本书为止。

现在，K小姐想知道经过这样的整理后，书架上最少会剩下多少本书。

输入格式

第一行包含三个整数 、 和 ，分别表示初始的书本数量、每次选择的书本数量和允许的最大编号差值。

第二行包含 个整数，表示每本书的编号。

输出格式

输出一个整数，表示经过整理后，书架上最少剩余的书本数量。

样例输入

4 3 3
1 2 3 6

样例输出

3

数据范围

• 
• 
• 
• 每本书的编号为不超过 的正整数

题解

滑动窗口+贪心

题目的核心要求：每次从 本书中移除编号最小的一本。这意味着我们应该尽可能多地执行这个操作，以最小化剩余的书本数量。

解题思路如下：

1. 将所有书的编号排序。这样可以保证每次都能选到编号最小的书。
2. 使用滑动窗口的方法，检查每个长度为 的连续子序列。
3. 对于每个窗口，如果最大编号和最小编号的差值不超过 ，那么我们就可以执行一次操作，移除一本书。
4. 统计可以执行操作的次数，最后剩余的书本数量就是初始数量减去操作次数。

间复杂度分析：

• 排序的时间复杂度是 。
• 滑动窗口的过程是线性的，时间复杂度为 。

因此，总的时间复杂度是 ，这对于给定的数据范围（）是可以接受的。

参考代码

• Python

# 读取输入
n, m, k = map(int, input().split())
books = list(map(int, input().split()))

# 对书本编号进行排序
books.sort()

# 初始化结果和滑动窗口的左右指针
result = n
left = 0

# 遍历所有可能的窗口
for right in range(n):
    # 当窗口大小达到 m 时
    if right - left + 1 == m:
        # 检查窗口内的最大和最小编号差是否不超过 k
        if books[right] - books[left] <= k:
            result -= 1  # 可以执行一次操作，减少一本书
        left += 1  # 移动左指针

# 输出结果
print(result)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        
        int[] books = new int[n];
        for (int i = 0; i < n; i++) {
            books[i] = scanner.nextInt();
        }
        
        // 对书本编号进行排序
        Arrays.sort(books);
        
        // 初始化结果和滑动窗口的左指针
        int result = n;
        int left = 0;
        
        // 遍历所有可能的窗口
        for (int right = 0; right < n; right++) {
            // 当窗口大小达到 m 时
            if (right - left + 1 == m) {