笔试时间：2025年03月12 春招实习

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：因为山就在那里

作为一个登山爱好者，Bob现在正计划向珠峰发起挑战，要问为什么的话，因为山就在那里！珠峰的气候变幻莫测，并不是每天都适合登山，但Bob通过东方神秘力量了解到接下来有n个特定日期可能会是适合登山的好日子。因此他在这n天一定要在珠峰大本营等待良机。然而，海拔5200米的珠峰大本营不是久居之地。根据医生的评估，Bob最多能够在此处生活的总天数为k天，否则出现生命危险的概率将大大增加。因此Bob需要注意在不适合登山的日子下撤回低海拔地区。下撤回低海拔地区和前往珠峰大本营的旅费不可小觑，Bob自身也讨厌频繁移动。因此请你告诉他，在不错过n个特定日期，同时在珠峰大本营生活不超过总共k天的前提下，最少需要多少次移动？注意，Bob一开始位于低海拔地区，最终也必须回到低海拔地区。一次移动指的是单程而非往返，即从低海拔地区前往珠峰大本营或从珠峰大本营下撤回低海拔地区分别是一次移动。

输入描述

第一行两个正整数n，k，表示可能适合登山的日子天数和Bob最多能在珠峰大本营生活的天数 ;

第二行n个正整数ai，表示第i个可能适合登山的日子是接下来的第ai天，保证递增。

输出描述

一行，输出一个正整数，表示最少的移动次数。

样例输入

5 8

2 3 5 6 10

样例输出

4

参考题解

C++：[此代码未进行大量数据的测试，仅供参考]

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int tot = a.back() - a[0] + 1;
    vector<int> df;
    for (int i = 0; i < n - 1; ++i) {
        int gap = a[i + 1] - a[i] - 1;
        if (gap > 0) {
            df.push_back(gap);
        }
    }
    sort(df.begin(), df.end());
    int cnt = 0;
    while (true) {
        if (tot <= k) break;
        if (df.empty()) break;
        tot -= df.back();
        cnt += 2;
        df.pop_back();
    }
    cout << cnt + 2 << endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        
        // 初始段数 tot = a[n-1] - a[0] + 1
        int tot = a[n-1] - a[0] + 1;
        
        // 记录相邻元素间的 gap
        List<Integer> df = new ArrayList<>();
        for(int i = 0; i < n-1; i++){
            int gap = a[i+1] - a[i] - 1;
            if(gap > 0){
                df.add(gap);
            }
        }
        
        // gap 排序
        Collections.sort(df);
        
        int cnt = 0;
        // 从最大的 gap 开始减少 tot，直到 tot <= k 或没剩 gap
        while(true) {
            if(tot <= k) break;
            if(df.isEmpty()) break;
            
            // 取最大的 gap
            int g = df.remove(df.size() - 1);
            tot -= g;
            cnt += 2;
        }
        
        // 输出结果
        System.out.println(cnt + 2);
        
        sc.close();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def solve():
    import sys
    data = sys.stdin.read().strip().split()
    # 如果要行读取，也可以用 sys.stdin.readline
    
    n = int(data[0])
    k = int(data[1])
    a = list(map(int, data[2:]))

    # 初始段数
    tot = a[-1] - a[0] + 1
    
    # 收集相邻间的 gap
    df = []
    for i in range(n - 1):
        gap = a[i+1] - a[i] - 1
        if gap > 0:
            df.append(gap)
    
    # 排序 gap
    df.sort()
    
    cnt = 0
    # 从最大的 gap 开始尝试减少 tot
    while True:
        if tot <