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

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

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

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

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

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

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

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

🌈 花子(海外留学生版)秋招笔试，来啦！！！

🧸 强烈建议国内的宝子也刷一刷 海外版本 的，以下是一些数据

• 海外 0924 第一题 国内 0927 第二题
• 海外 0924 第二题 国内 1012 第一题
• 海外 0924 第三题 国内 1009 第三题
• 海外 1009 第三题 国内 1016 第三题
• 

无须多言，冲 🐛🐛🐛 就完事了！！！！

1️⃣ 比较基础的大根堆的应用

2️⃣ 直接暴力枚举/双指针+滑动窗口

3️⃣ 思维+贪心+分类讨论

🎫 01.智能家居定时系统评测链接🔗

题目描述

K小姐最近购买了一套智能家居系统。该系统有一个定时控制功能,可以设置多个定时任务来控制各种家电设备。系统的特点如下:

1. 系统精度为1分钟,最多可以设置 个定时任务。
2. 每个任务包含一个执行时间 (整数,表示从当前时刻起多少分钟后执行)。
3. 如果多个任务在同一时刻执行,按照添加顺序依次执行。
4. 当系统中任务数少于 个时,可以直接添加新任务。
5. 当系统中已有 个任务时,如果新任务执行时间晚于系统中最晚的任务,则丢弃新任务;否则,删除系统中最晚的任务,添加新任务。

现在K小姐想要一次性添加 个定时任务。请你帮她计算出,最终系统中最晚执行的任务是第几个添加的。

输入格式

第一行包含一个正整数 ,表示系统最多可以设置的任务数。

第二行包含一个正整数 ,表示K小姐想要添加的任务数。

第三行包含 个正整数,表示每个任务的执行时间 。

输出格式

输出一个整数,表示最终系统中最晚执行的任务是第几个添加的(编号从0开始)。如果有多个任务同时是最晚执行的,输出编号最大的那个。

样例输入1

2
12
1 2 3 4 6 19 20 21 22 23 25 1

样例输出1

11

样例输入2

1
2
10 2

样例输出2

1

样例输入3

20
5
1 2 3 4 5

样例输出3

4

样例解释

数据范围

题解

堆模拟

这道题目本质上是在模拟一个固定容量的优先队列。维护一个大小为 的优先队列,队列中的元素按照执行时间从早到晚排序。同时还需要记录每个任务的添加顺序。

解题思路如下:

1. 创建一个优先队列,用于存储任务。队列中的每个元素是一个二元组 ,其中 是执行时间, 是添加顺序。

2. 遍历所有要添加的任务:

   • 如果队列大小小于 ,直接将任务加入队列。
   • 如果队列已满:
     • 比较新任务的执行时间和队列中最晚任务的执行时间。
     • 如果新任务执行时间不晚于队列中最晚任务,则移除队列中最晚的任务,添加新任务。
     • 否则,丢弃新任务。

3. 遍历结束后,队列中执行时间最晚的任务就是我们要找的。如果有多个任务执行时间相同且最晚,我们需要返回添加顺序最大的那个。

时间复杂度分析:

• 对于每个任务,我们需要进行一次优先队列的操作(插入或删除),时间复杂度为 。
• 总共有 个任务,所以总的时间复杂度为 。

考虑到 且 ,这个时间复杂度是可以接受的。

参考代码

• Python

# 使用优先队列解决定时任务问题
from heapq import heappush, heappop, heapreplace

def solve():
    # 读取输入
    n = int(input())  # 系统容量
    m = int(input())  # 任务数量
    tasks = list(map(int, input().split()))  # 任务执行时间列表
    
    # 初始化优先队列
    q = []
    
    # 处理每个任务
    for i, val in enumerate(tasks):
        if len(q) < n:
            # 队列未满,直接添加任务
            heappush(q, (-val, -i))
        else:
            # 队列已满,判断是否需要替换
            if -q[0][0] >= val:
                # 当前任务执行时间不晚于队列中最晚的任务
                heapreplace(q, (-val, -i))
    
    # 输出最晚任务的索引
    print(-q[0][1])

if __name__ == "__main__":
    solve()

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入
        int n = sc.nextInt();  // 系统容量
        int m = sc.nextInt();  // 任务数量
        
        // 创建优先队列,按照时间降序排列,时间相同按索引降序
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return Long.compare(a[0], b[0]);
            }
            return Long.compare(a[1], b[1]);
        });
        
        // 处理每个任务
        for (int i = 0; i < m; i++) {
            long val = sc.nextLong();
            if (pq.size() < n) {
                // 队列未满,直接添加任务
                pq.offer(new long[]{-val, -i});
            } else {
                // 队列已满,判断是否需要替换
                if (-pq.peek()[0] >= val) {
                    pq.poll();
                    pq.offer(new long[]{-val, -i});
                }
            }
        }
        
        // 输出最晚任务的索引
        System.out.println(-pq.peek()[1]);
    }
}

• Cpp

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    int n, m;
    cin >> n >> m;
    
    // 创建优先队列,pair的first存储时间,second存储索引
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    
    // 处理每个任务
    for (int i = 0; i < m; i++) {
        ll val;
        cin >> val;
        if (pq.size() < n) {
            // 队列未满,直接添加任务
            pq.push({-val, -i});
        } else {
            // 队列已满,判断是否需要替换
            if (-pq.top().first >= val) {
                pq.pop();
                pq.push({-val, -i});
            }
        }
    }
    
    // 输出最晚任务的索引
    cout << -pq.top().second << endl;
    
    return 0;
}

🦸‍♂️ 02.智能系统优化 评测链接🔗

问题描述

LYA 公司正在开发一款智能家居系统。该系统由多个智能设备组成，每个设备都可以在两种模式下运行：高性能模式和节能模式。在高性能模式下，设备的响应速度更快，但能耗较高；在节能模式下，设备的响应速度较慢，但能耗较低。

系统中有两种处理单元：主处理器和辅助处理器。主处理器的处理速度是辅助处理器的 6 倍，但能耗也相应更高。为了优化系统性能和能耗，LYA 公司需要合理分配设备的运行模式。

系统优化的目标是：最小化整体响应时间，同时平衡两种处理器的负载。整体响应时间定义为：max(主处理器总处理时间，辅助处理器总处理时间)。

为简化问题，我们假设：

1. 每个设备只能在一种模式下运行。
2. 分配给辅助处理器的设备必须是连续的。

输入格式

第一行输入一个整数 ，表示智能设备的数量。

第二行输入 个整数，表示每个设备在主处理器上的处理时间 。

输出格式

输出一个整数，表示系统的最小整体响应时间。

样例输入1

9
1 2 3 4 5 6 7 8 9

样例输出1

39

样例输入2

9
3 2 17 8 3 5 4 18 15

样例输出2

66

样例解释

样例1	将第 6 个设备（处理时间为 6）分配给辅助处理器，其处理时间变为 。其余设备分配给主处理器，总处理时间为 。整体响应时间为 max(39, 36) = 39。
样例2	将第 4 和第 5 个设备（处理时间分别为 8 和 3）分配给辅助处理器，总处理时间为 。其余设备分配给主处理器，总处理时间为 。整体响应时间为 max(64, 66) = 66。

数据范围

题解

双指针

这道题目本质上是一个最大子数组问题的变种。需要找到一个连续的子数组，使得将这个子数组中的元素分配给辅助处理器后，能够最小化整体响应时间。

关键思路是使用滑动窗口算法。维护一个窗口，表示分配给辅助处理器的设备。窗口的和乘以 6 就是辅助处理器的处理时间，窗口外的和就是主处理器的处理时间。

算法步骤如下：

1. 初始化左右指针 left 和 right，都指向数组开始。
2. 计算整个数组的和 total_sum，这是所有设备都分配给主处理器的情况。
3. 使用滑动窗口，不断移动右指针：
   • 如果当前窗口和的 6 倍小于 total_sum 的 1/7，继续扩大窗口。
   • 否则，开始移动左指针，缩小窗口。
4. 在这个过程中，不断更新最小的整体响应时间。

这个算法的时间复杂度是 O(n)，因为每个元素最多被访问两次（一次被右指针，一次被左指针）。空间复杂度是 O(1)，只使用了常数额外空间。

对于给定的数据范围（），这个线性时间复杂度的算法是完全可以接受的，能够在较短时间内得出结果。

参考代码

• Python

# 导入系统模块
import sys

# 定义输入函数
input = lambda: sys.stdin.readline().strip()

def solve(times, total):
    """
    计算最优执行时间
    Args:
        times: 每个算子在矩阵计算单元的执行时间列表
        total: 所有算子在矩阵计算单元的总执行时间
    Returns:
        最小的总体执行时间
    """
    threshold = total / 7
    min_time = min(total, 6 * total)
    
    left = window_sum = 0
    for right in range(len(times)):
        window_sum += times[right]
        
        while left <= right and window_sum > threshold:
            vector_time = 6 * window_sum
            matrix_time = total - window_sum
            min_time = min(min_time, max(matrix_ti