✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

滴滴

题目一：小毛的技能训练计划

1️⃣：维护前缀和与前缀最大值，判断是否可以"摸鱼"

2️⃣：利用条件 sum ≤ K 或 maxVal ≥ sum - K 来确定可行性

难度：中等

这道题目的关键在于理解"摸鱼"策略的作用。对于每个前缀，我们可以选择不学习其中强度最大的课程，从而用有限的精力学习更多课程。通过维护前缀和与前缀最大值，我们可以在 O(n) 时间内找到最优解。

题目二：小兰的图书馆探险

1️⃣：使用滑动窗口技术找到包含所有书籍类型的最小区间

2️⃣：对每个区间计算移动成本：区间长度 + 到最近端点的距离

3️⃣：取所有可行区间中移动成本最小的方案

难度：中等偏难

这道题目是经典的"最小覆盖区间"问题的应用。需要理解最优移动策略：先走到距离起始位置最近的区间端点，再遍历到另一端。通过双指针技术，我们可以高效地找到所有候选区间并计算最优解。

01. 小毛的技能训练计划

问题描述

小毛是一名程序员，最近他决定通过一系列在线课程来提升自己的技能。这些课程必须按照顺序学习，第 门课程的学习强度为 。

由于工作繁忙，小毛的学习精力有限，他希望从第一门课程开始连续学习若干门课程，使得所有课程的学习强度总和不超过 。

不过小毛很聪明，他发现可以对其中最多一门课程"摸鱼"（即该课程的学习强度可以视为 ），这样就能学习更多的课程了。

请问在这种策略下，小毛最多能学习多少门课程？

输入格式

第一行包含一个整数 ，表示测试数据的组数。

对于每组测试数据：

第一行包含两个整数 和 ，分别表示课程总数和小毛的学习精力上限。

第二行包含 个整数 ，表示每门课程的学习强度。

输出格式

输出 行，每行包含一个整数，表示小毛在对应测试数据中最多能学习的课程数量。

样例输入

2
7 10
1 2 3 4 5 6 7
1 1
1 1 1 1 1

样例输出

5
1

数据范围

样例	解释说明
样例1	小毛可以学习前5门课程 ，总强度为15，但他可以对第5门课程"摸鱼"，这样实际强度为10，恰好满足要求
样例2	由于每门课程强度都是1，而精力上限也是1，小毛只能学习1门课程（可以"摸鱼"）

题解

这道题的关键在于理解"摸鱼"策略的作用。我们需要找到最长的前缀，使得要么前缀和不超过 ，要么去掉前缀中某个元素后和不超过 。

让我们定义前缀和 。

对于位置 ，有两种情况：

1. 不使用"摸鱼"策略：要求
2. 使用"摸鱼"策略：选择前缀中的某个元素 作为"摸鱼"对象，要求

对于第二种情况，为了让 成立，我们需要 。显然，选择前缀中的最大元素作为"摸鱼"对象是最优的。

因此，算法思路如下：

1. 维护当前的前缀和 和前缀中的最大值
2. 对于每个位置 ，检查是否满足 或
3. 如果满足条件，则位置 是可行的，更新答案

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

参考代码

• Python

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

def solve():
    t = int(input())
    for _ in range(t):
        n, k = map(int, input().split())
        a = list(map(int, input().split()))
        
        # sum_val: 前缀和, max_val: 前缀最大值
        sum_val, max_val = 0, 0
        ans = 0
        
        for i in range(n):
            sum_val += a[i]  # 更新前缀和
            max_val = max(max_val, a[i])  # 更新前缀最大值
            
            # 检查当前前缀是否可行
            if sum_val <= k or max_val >= sum_val - k:
                ans = i + 1  # 更新最长可行前缀长度
        
        print(ans)

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;
        long long k;
        cin >> n >> k;
        
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        long long sum_val = 0, max_val = 0;  // sum_val: 前缀和, max_val: 前缀最大值
        int ans = 0;
        
        for (int i = 0; i < n; i++) {
            sum_val += a[i];  // 更新前缀和
            max_val = max(max_val, a[i]);  // 更新前缀最大值
            
            // 检查当前前缀是否可行
            if (sum_val <= k || max_val >= sum_val - k) {
                ans = i + 1;  // 更新最长可行前缀长度
            }
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int t = Integer.parseInt(br.readLine());
        
        while (t-- > 0) {
            String[] line1 = br.readLine().split(" ");
            int n = Integer.parseInt(line1[0]);
            long k = Long.parseLong(line1[1]);
            
            String[] line2 = br.readLine().split(" ");
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {