程序员基德

04-01 19:43 中国科学技术大学 C++ 发布于浙江

关注

【春招笔试】2025.03.29-美团研发岗改编题

✅ 春招备战指南 ✅

💡 学习建议：

先尝试独立解题（建议用时：90分钟/套）
对照解析查漏补缺
配套练习题库

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

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

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

题目一：班级值班安排优化

1️⃣：计算员工值班时间总和

2️⃣：直接比较 n*k 与总和的大小关系

难度：简单

这道题目的核心在于数学模型的简化。通过分析平均分配的本质，我们发现只需直接比较员工数量与时间上限的乘积(n*k)和总工作时间即可得出结论，无需计算向上取整的平均值。这种优化不仅减少了计算步骤，避免了除法运算和向上取整的复杂性，还提高了代码的可读性和执行效率。时间复杂度为O(n)，是解决资源分配类问题的典型数学思维应用。

题目二：二进制数值合成统计

1️⃣：理解数字的二进制表示与"合成度"概念

2️⃣：计算每个数的二进制中1的个数

3️⃣：确定可能的合成度范围并统计结果

难度：中等

这道题目考察位运算的灵活应用和数学分析能力。关键突破口在于发现数字的合成度范围与其二进制表示中1的个数密切相关，通过分析可得出确切的上下界。实现上采用快速位计数技术，如Brian Kernighan算法或查表法，可以高效计算二进制中1的数量。算法避开了暴力枚举所有可能表示方法的陷阱，将时间复杂度优化至O(n)，体现了位运算在特定问题上的强大能力和算法设计中数学分析的重要性。

题目三：激光雕刻路径优化

1️⃣：计算每个多边形的周长与切割时间

2️⃣：使用深度优先搜索(DFS)遍历所有多边形切割顺序

3️⃣：使用动态规划找到最优的起点选择策略

难度：困难

这道题目展示了组合优化问题的高级解决思路。算法使用DFS代替简单的排列枚举，为每个切割顺序使用动态规划寻找最优起点策略。DFS实现相比于列举所有排列有三大优势：(1)通过状态判断可以实现提前剪枝，减少不必要的搜索；(2)避免了预生成全部排列的内存开销；(3)便于在搜索过程中融入更多优化策略。动态规划部分精确建模了状态转移关系，通过记忆化避免重复计算。尽管最坏时间复杂度仍为O(n!×m²)，但优化的搜索策略在实际运行中可显著提升效率，是解决组合优化类问题的典范。

整体评价

这四道题目难度递增，覆盖了多种算法思想，展现了不同程度的代码优化实践：

简化数学模型：第一题展示了如何将看似复杂的平均值计算优化为简单的不等式比较(n*k ≥ 总工作时间)，大幅简化了代码实现并提高了可读性。
多种实现方案：第二题提供了两种解决方案 - 基于NumPy的矩阵求解和自实现的高斯消元法，体现了在工程实践中平衡依赖性与实现复杂度的思考。
位运算优化：第三题利用位运算和数学分析，避免了暴力枚举，体现了位运算在特定问题上的优势。
搜索优化：第四题从排列枚举优化为DFS搜索，不仅提高了搜索效率，还为未来可能的剪枝优化打下基础，体现了解决组合优化问题的进阶思想。

这组题目从数学分析、数值计算、位运算到组合优化与动态规划，层层递进，涵盖了算法设计中的多种基本技巧和高级策略。对于系统学习算法与提升实现能力都有很好的训练价值，特别适合作为算法学习的实践案例。

01. 班级值班安排优化

问题描述

公司正在为员工安排每日值班表。每位员工每天需要值班 $a_i$ 小时，但是公司关心员工的工作生活平衡，希望员工每天的值班时间不要过长。

公司规定了一个阈值 $k$ ，表示每天最多值班 $k$ 小时才能保证员工的身心健康。由于工作需求，总的值班时间必须保持不变，但是公司允许员工之间进行调休安排，即某位员工的部分值班时间可以由其他员工承担。

现在请你帮助判断，在总值班时间不变的情况下，是否能够通过合理安排，使得所有员工每天的值班时间都不超过 $k$ 小时。

输入格式

每个测试文件包含多组测试数据。第一行输入一个整数 $T (1 \leq T \leq 1000)$ ，代表数据组数。

对于每一组测试数据：

第一行包含两个整数 $n, k (1 \leq n \leq 10^5, 1 \leq k \leq 24)$ ，分别表示员工人数和每天最长值班时间限制。

第二行包含 $n$ 个整数，第 $i$ 个数为 $a_i (1 \leq a_i \leq 24)$ ，表示第 $i$ 位员工原定的值班时长。

数据保证单个测试文件中 $\sum n \leq 10^5$ 。

输出格式

共 $T$ 行，每行一个字符串，若能完成调休使得所有员工的值班时间都不超过 $k$ ，输出 " $YES$ "，否则输出 " $NO$ "。

样例输入

样例输出

YES
NO

样例解释说明

样例1	在第一组数据中，只有一名员工，值班时间为2小时，未超过限制的2小时，所以输出YES。
样例2	在第二组数据中，总值班时间为1+3=4小时，员工人数n=2，每人最多可以值班k=2小时。由于n*k=4等于总值班时间，可以安排每人值班2小时，所以应该输出YES。

数据范围

$1 \leq T \leq 1000$
$1 \leq n \leq 10^5$
$1 \leq k \leq 24$
$1 \leq a_i \leq 24$
$\sum n \leq 10^5$

题解

这道题目考察的是如何判断在总时间不变的情况下，能否通过重新分配值班时间使得所有员工的工作时间不超过给定的阈值。

首先，我们思考一下什么样的情况下重新分配是可行的。总的值班时间是固定的，等于所有 $a_i$ 的总和，记为 $sumA$ 。在最优的分配方案中，我们肯定希望尽可能平均地分配这些时间给 $n$ 个员工。

现在考虑一下极限情况：如果每个员工都使用最大允许的时间 $k$ ，那么 $n$ 个员工总共可以承担的最大工作时间是 $n \times k$ 。只有当总工作时间 $sumA$ 不超过 $n \times k$ 时，才有可能合理分配任务使得每个员工的工作时间不超过 $k$ 。

因此，问题简化为判断： $sumA \leq n \times k$ 是否成立。

这种方法比之前计算向上取整的平均值更加直观，也避免了除法运算和向上取整的复杂度。可以证明，两种方法在数学上是等价的。

时间复杂度分析：对于每组测试数据，我们只需要计算数组和并与 $n \times k$ 比较，复杂度为 $O(n)$ ，总体复杂度为 $O(T \times n)$ ，其中 $T$ 为测试组数， $n$ 为每组的数组长度。

空间复杂度：只需要存储输入数组和计算和，复杂度为 $O(n)$ 。

参考代码

Python

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

def judge():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    # 计算总时间
    tot = sum(a)
    
    # 判断总时间是否超过n*k
    return "YES" if tot <= n * k else "NO"

t = int(input())
for _ in range(t):
    print(judge())

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;  // 读取测试组数
    
    while (t--) {
        int n, k;
        cin >> n >> k;  // 读取员工数和时间限制
        
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            int hrs;
            cin >> hrs;
            sum += hrs;  // 累加总时间
        }
        
        // 判断总时间是否不超过n*k
        if (sum <= (long long)n * k) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();  // 测试组数
        
        while (t-- > 0) {
            int n = scan.nextInt();  // 员工数
            int k = scan.nextInt();  // 时间限制
            
            long sum = 0;
            for (int i = 0; i < n; i++) {
                int hrs = scan.nextInt();
                sum += hrs;  // 累加总时间
            }
            
            // 判断总时间是否不超过n*k
            System.out.println(sum <= (long)n * k ? "YES" : "NO");
        }
        
        scan.close();
    }
}

02. 二进制数值合成统计

问题描述

小基是一名对数字极为敏感的程序设计师，他发现了一种有趣的数值特性：任何正整数都可以表示为若干个2的幂次之和。例如，数字13可以表示为 $13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0$ 。

他将这种表示方式中使用的2的幂次数量称为该数字的"合成度"。如果一个数字可以用恰好 $k$ 个2的幂次之和表示，则称该数字具有" $k$ 合成度"。需要注意的是，同一个2的幂次可以多次使用。

例如，数字9可以表示为：

$9 = 8 + 1 = 2^3 + 2^0$ ，因此9具有2合成度
$9 = 4 + 4 + 1 = 2^2 + 2^2 + 2^0$ ，因此9也具有3合成度
$9 = 4 + 2 + 2 + 1 = 2^2 + 2^1 + 2^1 + 2^0$ ，因此9也具有4合成度
以此类推...

现在，给定一个整数数组，小基想要统计具有1合成度、2合成度、...、30合成度的数字各有多少个。请你帮他完成这个统计任务。

输入格式

第一行包含一个整数 $n (1 \leq n \leq 2×10^5)$ ，表示数组中的元素数量。

第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n (0 \leq a_i \leq 10^9)$ ，表示给定的数组。

输出格式

输出一行，包含30个整数，依次表示具有1合成度、2合成度、...、30合成度的数字数量。

样例输入

3
1 2 3

样例输出

2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

样例解释说明

样例1	数组[1,2,3]中：数字1可表示为 $2^0$ ，具有1合成度数字2可表示为 $2^1$ ，具有1合成度数字3可表示为 $2^1+2^0$ ，具有2合成度；也可表示为 $2^0+2^0+2^0$ ，具有3合成度因此，具有1合成度的数字有2个(1和2)，具有2合成度的数字有2个(2和3)，具有3合成度的数字有1个(3)，其余合成度的数字数量都是0

数据范围

$1 \leq n \leq 2×10^5$
$0 \leq a_i \leq 10^9$

题解

这道题目要求我们统计一个数组中具有不同"合成度"的数字数量。一个数字的"合成度"定义为表示该数字所需的2的幂次数量。

首先，我们需要理解几个关键性质：

任何正整数的标准二进制表示就是一种使用2的幂次之和的方式，其中每个2的幂次恰好使用一次。例如，13的二进制是1101，表示 $13 = 2^3 + 2^2 + 2^0$ 。
对于一个数字a，其二进制表示中1的个数（即二进制中位权为1的位数）就是表示a所需的最少2的幂次数量。这个性质源于二进制的唯一性。
通过将某些2的幂次分解成更小的幂次之和，我们可以增加使用的2的幂次数量。例如， $2^3 = 2^2 + 2^2$ ，所以可以用更多的幂次表示同一个数。
理论上，任何正整数a最多可以用a个 $2^0$ （即a个1）表示。但题目限制了只需考虑到30合成度。

基于以上性质，我们可以得出一个重要结论：对于任意正整数a，其可能的合成度k的范围是： $\text{popcount}(a) \leq k \leq \min(a, 30)$

其中 $\text{popcount}(a)$ 表示a的二进制表示中1的个数。

算法思路如下：

初始化一个长度为31的数组ans（下标从1到30），用于统计各个合成度的数字数量。
对于数组中的每个非零数字a：
- 计算a的二进制中1的个数，记为ones。
- 确定a的最大可能合成度R = min(a, 30)。
- 对于k从ones到R，将ans[k]加1。
最后输出ans数组的1到30位置的值。

时间复杂度分析：

对于每个数字，计算二进制中1的个数需要O(log a)的时间。
对于每个数字，更新合成度计数需要O(min(a, 30))的时间。
总体时间复杂度为O(n * (log a_max + min(a_max, 30)))，其中a_max是数组中的最大值。
由于a最大为10^9，log a_max约为30，并且min(a_max, 30)最大为30，所以时间复杂度可以近似为O(60n)，对于n ≤ 2*10^5的规模来说是可以接受的。

空间复杂度：只需要O(1)的额外空间来存储结果数组（大小为31）。

参考代码

Python

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

def count_harmonics():
    n = int(input())
    nums = list(map(int, input().split()))
    
    # 初始化结果数组，下标1到30表示对应的合成度
    res = [0] * 31
    
    for num in nums:
        if num == 0:
            continue  # 0不计入统计
        
        # 计算num的二进制中1的个数（最小合成度）
        min_k = bin(num).count('1')
        
        # 最大可能的合成度
        max_k = min(num, 30)
        
        # 更新所有可能的合成度计数
        for k in range(min_k, max_k + 1):
            res[k] += 1
    
    # 输出结果
    print(' '.join(str(res[k]) for k in range(1, 31)))

count_harmonics()

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

int count_bits(int n) {
    int cnt = 0;
    while (n) {
        cnt += n & 1;
        n >>= 1;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 初始化结果数组，下标1到30表示对应的合成度
    vector<int> res(31, 0);
    
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        
        if (num == 0) continue; // 0不计入统计
        
        // 计算num的二进制中1的个数（最小合成度）
        int min_k = __builtin_popcount(num);
        
        // 最大可能的合成度
        int max_k = min(num, 30);
        
        // 更新所有可能的合成度计数
        for (int k = min_k; k <= max_k; k++) {
            res[k]++;
        }
    }
    
    // 输出结果
    for (int k = 1; k <= 30; k++) {
        cout << res[k];
        if (k < 30) cout << " ";
    }
    cout << endl;
    
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 初始化结果数组，下标1到30表示对应的合成度
        int[] res = new int[31];
        
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            
            if (num == 0) continue; // 0不计入统计
            
            // 计算num的二进制中1的个数（最小合成度）
            int minK = Integer.bitCount(num);
            
            // 最大可能的合成度
            int maxK = Math.min(num, 30);
            
            // 更新所有可能的合成度计数
            for (int k = minK; k <= maxK; k++) {
                res[k]++;
            }
        }
        
        // 输出结果
        StringBuilder sb = new StringBuilder();
        for (int k = 1; k <= 30; k++) {
            sb.append(res[k]);
            if (k < 30) sb.append(" ");
        }
        System.out.println(sb.toString());
        
        sc.close();
    }
}


---

# 03. 激光雕刻路径优化

## 问题描述

小柯是一家设计工作室的设计师，她需要使用激光雕刻机制作一批精美的图案。每个图案由若干个闭合的多边形组成，激光雕刻机需要依次切割这些多边形。

激光雕刻机的工作原理如下：
1. 激光头可以从平面上任意一点开始工作
2. 对于每个多边形，激光头必须先移动到该多边形上的某一个点作为起点
3. 激光头以不同的速度沿着多边形的边缘移动，完整切割一周后回到起点
4. 切割完所有图形后，激光头需要返回最初的起点

为了提高效率，小柯希望找到一种最优的多边形切割顺序和每个多边形的起点选择，使得整个雕刻过程所需的总时间最短。

具体来说，激光头有两种速度：
- 不切割时的移动速度为 $x$ 单位长度/秒
- 切割第 $i$ 个多边形时的速度为 $y_i$ 单位长度/秒

小柯需要你的帮助来计算最短的雕刻时间。

## 输入格式

第一行包含两个整数 $n, x(3 \leq n \leq 7; 1 \leq x \leq 1000)$，分别表示多边形的数量和激光头不切割时的移动速度。

第二行包含 $n$ 个整数 $y_1, y_2, ..., y_n(1 \leq y_i \leq 1000)$，表示激光头切割第 $i$ 个多边形时的速度。

接下来描述 $n$ 个多边形，对于第 $i$ 个多边形：
- 第一行包含一个整数 $m_i(3 \leq m_i \leq 7)$，表示多边形的顶点数量。
- 接下来 $m_i$ 行，每行包含两个整数 $a, b(-1000 \leq a, b \leq 1000)$，表示一个顶点的坐标 $(a, b)$。

保证同一个多边形内没有重复的点。

## 输出格式

输出一个实数，表示最短的雕刻时间。

由于实数计算存在误差，当误差的量级不超过 $10^{-6}$ 时，答案将被接受。具体来说，设你的答案为 $a$，标准答案为 $b$，当且仅当 $\frac{|a-b|}{\max(1,|b|)} < 10^{-6}$ 时，你的答案将被接受。

## 样例输入

3 1 1 2 1 3 -3 3 0 0 -3 -2 3 1 3 3 0 1 -3 4 -2 1 4 3 5 -2 -3 -5


## 样例输出

54.507981260725

| 样例 | 解释说明 |
| -------- | ------ |
| 样例1 | 最优策略是：<br>1. 将激光头放置在点(0,0)作为初始点<br>2. 切割第一个多边形(起点为(0,0))，耗时12.84<br>3. 移动到第三个多边形(起点为(-2,1))，耗时2.24<br>4. 切割第三个多边形，耗时26.05<br>5. 移动到第二个多边形(起点为(1,3))，耗时3.16<br>6. 切割第二个多边形，耗时6.61<br>7. 返回初始点(0,0)，耗时3.61<br>总时间为54.51 |

## 数据范围
- $3 \leq n \leq 7$
- $1 \leq x \leq 1000$
- $1 \leq y_i \leq 1000$
- $3 \leq m_i \leq 7$
- $-1000 \leq a, b \leq 1000$

## 题解

这道题目是一个组合优化问题，我们需要找到一种最优的多边形切割顺序和起点选择策略。

先分析一下题目的关键点：
1. 我们需要决定切割多边形的顺序
2. 对于每个多边形，我们需要选择一个合适的起点
3. 最后需要返回初始点

这是一个复合的优化问题，让我们逐步拆解：

### 计算多边形的周长

首先，对于每个多边形，无论选择哪个点作为起点，切割整个多边形所需的时间都是固定的，即周长除以切割速度。我们需要计算每个多边形的周长

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

互联网刷题笔试宝典文章被收录于专栏

互联网刷题笔试宝典，这里涵盖了市面上大部分的笔试题合集，希望助大家春秋招一臂之力