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

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

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

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

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

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

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

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

🌈 京东秋招笔试，来啦！！！

🍥 本次的难度排序为 1 < 3 < 2，第二题是一个二分优化LIS的题目，之前没做过的小伙伴写了朴素的LIS会超时

1️⃣ 贪心，每次遇到超出限制的就建立新的组即可

2️⃣ 二分优化LIS，这个知识点秋招出现过两次了，之前有一道山峰的题也出现过

3️⃣ DFS + 哈希表，这题数据范围比较小，怎么做都可以，当然数据出到 也能做，不过难度较大感兴趣的小伙伴可以自行了解哦～

🎁 01.LYA的礼物分类 评测链接🔗

问题描述

LYA是一家礼品店的老板。她最近收到了一批新的礼物，想要将它们分类摆放在店里。每个礼物都有一个特定的价值，LYA希望将价值相近的礼物放在一起。

具体来说，LYA有 个礼物，第 个礼物的价值为 。她想要将这些礼物分成若干组，每组必须是连续的一段礼物。同时，为了保持每组礼物的价值相近，她规定了一个最大价值差 ，即同一组内任意两个礼物的价值差不能超过 。

LYA想知道，在满足上述条件的情况下，最少需要将礼物分成多少组？

输入格式

第一行包含两个整数 和 （，），分别表示礼物的数量和最大价值差。

第二行包含 个整数 （），表示每个礼物的价值。

输出格式

输出一个整数，表示最少需要分成的组数。

样例输入

4 1
1 3 1 4

样例输出

4

样例输入

4 2
1 3 1 4

样例输出

2

数据范围

• 
• 
• 

题解

贪心

从左到右遍历礼物，维护当前组的最小值和最大值，一旦发现加入新的礼物会导致最大值和最小值的差超过 ，就结束当前组，开始一个新的组。

参考代码

• Python

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

# 初始化变量
minv = maxv = a[0]  # 当前组的最小值和最大值
cnt = 1  # 组数

# 遍历所有礼物
for i in range(1, n):
    # 更新当前组的最小值和最大值
    minv = min(a[i], minv)
    maxv = max(a[i], maxv)
    
    # 如果当前组的价值差超过k，开始新的一组
    if maxv - minv > k:
        cnt += 1
        minv = maxv = a[i]

# 输出结果
print(cnt)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        
        // 初始化变量
        int minv = a[0];  // 当前组的最小值
        int maxv = a[0];  // 当前组的最大值
        int cnt = 1;  // 组数
        
        // 遍历所有礼物
        for (int i = 1; i < n; i++) {
            // 更新当前组的最小值和最大值
            minv = Math.min(a[i], minv);
            maxv = Math.max(a[i], maxv);
            
            // 如果当前组的价值差超过k，开始新的一组
            if (maxv - minv > k) {
                cnt++;
                minv = maxv = a[i];
            }
        }
        
        // 输出结果
        System.out.println(cnt);
    }
}

• Cpp

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k;
    cin >> n >> k;
    
    vector<int> a(n);
    for (int& x : a) cin >> x;
    
    // 初始化变量
    int minv = a[0];  // 当前组的最小值
    int maxv = a[0];  // 当前组的最大值
    int cnt = 1;  // 组数
    
    // 遍历所有礼物
    for (int i = 1; i < n; i++) {
        // 更新当前组的最小值和最大值
        minv = min(a[i], minv);
        maxv = max(a[i], maxv);
        
        // 如果当前组的价值差超过k，开始新的一组
        if (maxv - minv > k) {
            cnt++;
            minv = maxv = a[i];
        }
    }
    
    // 输出结果
    cout << cnt << "\n";
    
    return 0;
}

🚗 02.LYA的车队管理 评测链接🔗

问题描述

LYA是一家物流公司的车队管理员。公司有一条单向单车道的专用道路，目前有 辆车在这条道路上行驶。每辆车都有自己的位置 和速度 。

LYA发现，如果所有车辆都保持当前速度行驶，很可能会发生追尾事故。为了确保安全，她需要移除一些车辆。

现在，LYA想知道至少需要移除多少辆车，才能确保剩下的车辆不会发生碰撞？

输入格式

第一行包含一个整数 （），表示车辆的数量。

接下来的 行，每行包含两个整数 和 （），分别表示第 辆车的位置和速度。

保证所有 的值都不相同。

输出格式

输出一个整数，表示需要移除的最少车辆数量。

样例输入

3
-1 -1
0 0
1 1

样例输出

0

样例输入

3
-1 1
0 0
1 -1

样例输出

2

数据范围

• 
• 

题解

二分优化LIS(最长上升子序列)

这道题目的本质是寻找最长的不会发生碰撞的车辆序列。

先对车辆按照位置进行排序。这样可以确保我们按照车辆在道路上的顺序来处理它们。

排序后，可以将问题转化为寻找最长的递增子序列（LIS）。这里的"递增"指的是车速的递增。

Q: 为什么这样做是正确的？因为如果后面的车速度比前面的车速度快，那么它们最终会相撞。只有当后面的车速度不快于前面的车，它们才不会相撞。

可以使用经典的 LIS 算法来解决这个问题，但是由于数据范围较大（），需要使用二分查找来优化算法，使其达到 的时间复杂度。

维护一个数组 ，其中 表示长度为 的 LIS 的最后一个元素的最小值。遍历每辆车，用二分查找找到它在 中的位置，并更新 。

最后， 中非 的元素个数就是最长的不会发生碰撞的车辆序列长度。用总车辆数减去这个长度，就是需要移除的最少车辆数。

这个算法的时间复杂度是 ，主要来自排序和每次二分查找的开销。空间复杂度是 ，用于存储排序后的车辆信息和 数组。

参考代码

• Python

# 读取输入
n = int(input())
cars = []
for _ in range(n):
    x, v = map(int, input().split())
    cars.append((x, v))

# 按位置排序
cars.sort()

# 初始化 LIS 数组
t = [float('inf')] * n

# 计算 LIS
for _, v in cars:
    # 二分查找
    left, right = 0, n
    while left < right:
        mid = (left + right) // 2
        if t[mid] > v:
            right = mid
        else:
            left = mid + 1
    t[left] = v

# 计算需要移除的车辆数
remove_count = n - t.index(float('inf'))
print(remove_count)

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        // 存储车辆信息
        int[][] cars = new int[n][2];
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            cars[i][0] = Integer.parseInt(input[0]);
            cars[i][1] = Integer.parseInt(input[1]);
        }
        
        // 按位置排序
        Arrays.sort(cars, (a, b) -> Integer.compare(a[0], b[0]));
        
        // 初始化 LIS 数组
        int[] t = new int[n];
        Arrays.fill(t, Integer.MAX_VALUE);
        
        // 计算 LIS
        for (int[] car : cars) {
            int index = Arrays.binarySearch(t, car[1]);
            if (index < 0) {
                index = -(index + 1);
            }
            t[index] = car[1];
        }
        
        // 计算需要移除的车辆数