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

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 编程一对一辅导

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

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

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

🍒 小伙伴们心心念念的银行笔试，他来咯

🍉 本次题目难度适中

1️⃣ 第一题是个简单的滑动窗口，动态维护一长度为 k 区间的和， 如果不想这样写的朋友，也可以直接二分做

2️⃣ 第二题是一 思维题，分析出对应的性质之后，细节也需要注意，题目质量还是蛮高的。

🥝 01.K小姐的果园管理

问题描述

K小姐是一位热爱园艺的企业家，她拥有一个大型果园。果园里种植了 棵不同品种的果树，每棵树上都结满了果实。为了更好地管理果园，K小姐决定对果实进行分类采摘。

每个果实都有两个属性：所在的树编号 和成熟度 。K小姐计划在每棵树上选择一个成熟度范围为 的区间，只采摘该区间内的果实。

现在，K小姐想知道通过这种方法，她最多能采摘到多少个果实。请你帮助K小姐解决这个问题。

输入格式

第一行包含三个整数 、 和 ，分别表示果树的数量、果实的总数和可选择的成熟度区间长度。

接下来的 行，每行包含两个整数 和 ，分别表示每个果实所在的树编号和成熟度。

输出格式

输出一个整数，表示K小姐最多可以采摘到的果实数量。

样例输入

2 5 3
1 12
1 4
2 9
2 7
2 44

样例输出

3

数据范围

• 
• 
• 
• 
• 

题解

滑动窗口

需要将每棵树上的果实按成熟度排序。可以使用哈希表来存储每棵树的果实信息，然后对每棵树的果实列表进行排序。

对于每棵树，使用滑动窗口的方法来找出最佳的采摘区间。

具体做法是维护一个长度为 的窗口，统计窗口内果实的数量。

1. 在遍历每棵树的果实时，我们移动窗口并更新当前树的最大果实数量。窗口的左边界是当前果实的成熟度，右边界是左边界加上 。

2. 最后，将所有树的最大果实数量相加，即为答案。

时间复杂度分析：假设平均每棵树上有 个果实，排序的时间复杂度为 。

对于每棵树，我们需要遍历一次果实列表，时间复杂度为 。

总的时间复杂度为 。

参考代码

• Python

# 导入必要的模块
from collections import defaultdict

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

# 将果实信息存储到对应的树中
for _ in range(m):
    pos, h = map(int, input().split())
    trees[pos].append(h)

total_fruits = 0

# 遍历每棵树
for tree in trees.values():
    # 对树上的果实按成熟度排序
    tree.sort()
    
    max_fruits = 0
    left = 0
    
    # 使用滑动窗口统计最多可采摘的果实数
    for right in range(len(tree)):
        while tree[right] - tree[left] >= k:
            left += 1
        max_fruits = max(max_fruits, right - left + 1)
    
    # 将当前树的最大果实数加到总数中
    total_fruits += max_fruits

# 输出结果
print(total_fruits)

• 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));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int k = Integer.parseInt(input[2]);

        // 使用Map存储每棵树的果实信息
        Map<Integer, List<Integer>> trees = new HashMap<>();

        // 读取果实信息
        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");
            int pos = Integer.parseInt(input[0]);
            int h = Integer.parseInt(input[1]);
            trees.computeIfAbsent(pos, key -> new ArrayList<>()).add(h);
        }

        int totalFruits = 0;

        // 遍历每棵树
        for (List<Integer> tree : trees.values()) {
            Collections.sort(tree);
            int maxFruits = 0;
            int left = 0;

            // 使用滑动窗口统计最多可采摘的果实数
            for (int right = 0; right < tree.size(); right++) {
                while (tree.get(right) - tree.get(left) >= k) {
                    left++;
                }
                maxFruits = Math.max(maxFruits, right - left + 1);
            }

            totalFruits += maxFruits;
        }

        // 输出结果
        System.out.println(totalFruits);
    }
}

• Cpp

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

using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    // 使用哈希表存储每棵树的果实信息
    unordered_map<int, vector<int>> trees;

    // 读取果实信息
    for (int i = 0; i < m; i++) {
        int pos, h;
        cin >> pos >> h;
        trees[pos].push_back(h);
    }

    int total_fruits