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

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

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

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

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

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

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

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

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

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

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

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

本次的难度相对23号国内笔的相对较低

1️⃣ 模拟/数据结构+二分

2️⃣ DFS模拟即可

3️⃣ 贪心+优先队列

📦 01.集装箱智能堆放 评测链接🔗

问题描述

LYA 港口的智能物流系统需要对一批集装箱进行堆放优化。每个集装箱都有一个承重等级，决定了它上面最多可以堆放多少个集装箱。承重等级为 的集装箱最多可以承载 个集装箱。所有集装箱的底面积都是 个单位面积。现在需要设计一个堆放方案，使得这批集装箱占用的地面面积最小。

输入格式

输入为一行整数，数字之间用空格隔开，表示每个集装箱的承重等级。

输出格式

输出一个整数，表示最小占地面积。

样例输入1

0 2 1

样例输出1

1

样例输入2

1 2 1 2

样例输出2

2

样例解释

数据范围

• （承重等级）
• （集装箱数量）

题解

贪心/模拟+二分

这道题的核心思路是贪心算法。需要尽可能地将集装箱堆得更高，这样才能减少占地面积。

关键思路：

1. 首先将集装箱按承重等级排序
2. 使用二分查找找到最适合放置的堆，堆按照从大到小排序
3. 如果找不到合适的堆，就新开一个堆

时间复杂度分析：

• 排序需要
• 每个集装箱的放置需要二分查找，复杂度
• 总体复杂度为

参考代码

• Python

def solve():
    # 读取输入
    a = list(map(int, input().split()))
    # 按承重等级排序
    a.sort()
    # 存储每堆的高度
    q = []
    
    for i in a:
        found = False
        # 二分查找合适的堆
        l, r = 0, len(q) - 1
        while l < r:
            mid = (l + r) >> 1
            if q[mid] <= i:
                r = mid
            else:
                l = mid + 1
                
        # 如果没有合适的堆或当前堆不满足条件
        if not q or q[l] > i:
            q.append(1)
        else:
            q[l] += 1
            
    print(len(q))

if __name__ == "__main__":
    solve()

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取输入
        List<Integer> a = new ArrayList<>();
        while (sc.hasNextInt()) {
            a.add(sc.nextInt());
        }
        
        // 排序
        Collections.sort(a);
        List<Integer> q = new ArrayList<>();
        
        for (int i : a) {
            int l = 0, r = q.size() - 1;
            // 二分查找
            while (l < r) {
                int mid = (l + r) >> 1;
                if (q.get(mid) <= i) r = mid;
                else l = mid + 1;
            }
            
            if (q.isEmpty() || q.get(l) > i) {
                q.add(1);
            } else {
                q.set(l, q.get(l) + 1);
            }
        }
        
        System.out.println(q.size());
    }
}

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 存储集装箱承重等级
    vector<int> a;
    int x;
    
    // 读取输入
    while (cin >> x) {
        a.push_back(x);
    }
    
    // 排序
    sort(a.begin(), a.end());
    
    // 存储每堆的高度
    vector<int> q;
    
    for (int i : a) {
        int l = 0, r = q.size() - 1;
        // 二分查找合适的堆
        while (l < r) {
            int mid = l + r >> 1;
            if (q[mid] <= i) r = mid;
            else l = mid + 1;
        }
        
        // 创建新堆或在现有堆上添加
        if (q.empty() || q[l] > i) {
            q.push_back(1);
        } else {
            q[l]++;
        }
    }
    
    cout << q.size() << "\n";
    return 0;
}

📚 02.公司调用链分析 评测链接🔗

问题描述

LYA 公司的技术团队正在开发一个性能分析工具，用于分析软件运行过程中的函数调用关系。该工具通过采样分析得到了一棵调用树，每个节点代表一个函数调用链，并记录了该调用链被采样到的次数。现在需要计算每个节点包含其所有子调用链的总采样次数。

调用链是指从主函数到某个函数的调用路径。例如，如果函数 调用了函数 ，我们记作 ->。如果函数 又调用了函数 ，形成 ->->，则称后者是 -> 的子调用链。

输入格式

第一行为一个整数 ，表示调用树的节点总数。

第二行包含 个整数，表示按层序遍历得到的树结构。其中正整数表示节点的采样次数， 用于分隔每个节点的子节点序列。第 个 和第 个 之间的节点为第 个节点的子节点。

输出格式

输出一行 个整数，表示更新后的调用树。格式与输入保持一致。

样例输入1

6
5 -1 2 3 8 -1 -1 1 7 -1 -1 -1

样例输出1

26 -1 2 11 8 -1 -1 1 7 -1 -1 -1 

样例解释

数据范围

• 
• 采样次数

题解

DFS模拟

这道题本质上是在处理一棵树的后序遍历问题。对于每个节点，需要将其子树中所有节点的采样次数累加到该节点上。

关键点在于如何从输入格式构建树结构。输入使用了层序遍历加分隔符的方式，通过 来标记每个节点的子节点序列的边界。可以：

1. 用一个计数器记录当前处理到第几个节点
2. 遇到正数时存储节点值，并根据分隔符确定父子关系
3. 建图后使用DFS进行后序遍历，计算每个节点包含子树的总和

时间复杂度为 ，空间复杂度为 。对于给定的数据范围()完全可以接受。

参考代码

• Python

def solve():
    n = int(input())  # 读取节点数
    arr = list(map(int, input().split()))  # 读取树的序列化输入
    
    # 建图
    g = [[] for _ in range(n + 1)]  # 邻接表存储树
    cnt = [0] * (n + 1)  # 存储每个节点的采样次数
    p = 1  # 当前父节点编号
    c = 1  # 当前处理的节点编号
    
    # 解析输入，构建树结构
    for i in range(2 * n):
        if arr[i] < 0:
            p += 1
        else:
            cnt[c] = arr[i]
            if c > 1:
                g[p-1].append(c)
                g[c].append(p-1)
            c += 1
    
    # DFS计算每个节点包含子树的总采样次数
    def dfs(u, fa):
        for v in g[u]:
            if v != fa:
                dfs(v, u)
                cnt[u] += cnt[v]
    
    dfs(1, -1)  # 从根节点开始DFS
    
    # 按原格式输出结果
    vis = [False] * (n + 1)
    vis[1] = True
    print(cnt[1], -1, end=' ')
    
    for i in range(1, n + 1):
        if len(g[i]) > 1:
            for v in g[i]:
                if not vis[v]:
                    vis[v] = True
                    print(cnt[v], end=' ')
        if i