笔试时间：2025年11月08日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

星际快递公司有N个包裹需要派送，每个包裹有两种派送方式：

1. 常规派送（消耗较多燃料）
2. 虫洞派送（使用一个虫洞通行证，可以以消耗较少燃料的情况下完成派送）

当前快递飞船携带了X单位的燃料和Y张虫洞通行证。星际快递公司想要计算，在优先派送尽可能多包裹的情况下，最小的燃料消耗是多少，请你帮助他们计算一下。

输入描述

输出描述

一行，两个整数，空格分开，表示最多可派送的包裹数量及对应的最小燃料消耗。

样例输入

3 20 1

8 5

7 4

10 6

样例输出

2 12

参考题解

核心思路：这是一个二维费用背包问题的变形，需要在燃料和虫洞通行证的双重限制下，优先派送尽可能多的包裹，再求最小燃料消耗。

1. 状态定义：dp[i][j]表示派送i个包裹且使用了j张虫洞通行证时的最小燃料消耗
2. 状态转移： 常规派送：dp[i][j] = min(dp[i][j], dp[i-1][j] + A_m)虫洞派送：dp[i][j] = min(dp[i][j], dp[i-1][j-1] + B_m)（需j≥1）
3. 遍历顺序：采用倒序遍历，确保每个包裹只被计算一次
4. 结果提取：从最多包裹数开始向下检查，找到第一个燃料消耗不超过X的包裹数量

Python：

import sys

def solve():
    N, X, Y = map(int, sys.stdin.readline().split())
    packages = []
    for _ in range(N):
        packages.append(list(map(int, sys.stdin.readline().split())))
    
    INF = X + 1
    dp = [[INF] * (Y + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    
    for A_m, B_m in packages:
        for i in range(N, 0, -1):
            for j in range(Y, -1, -1):
                if dp[i - 1][j] != INF:
                    new_fuel = dp[i - 1][j] + A_m
                    dp[i][j] = min(dp[i][j], new_fuel)
                
                if j >= 1:
                    if dp[i - 1][j - 1] != INF:
                        new_fuel = dp[i - 1][j - 1] + B_m
                        dp[i][j] = min(dp[i][j], new_fuel)
    
    max_count = 0
    min_fuel = INF
    
    for i in range(N, -1, -1):
        current_min_fuel = INF
        found = False
        
        for j in range(Y + 1):
            if dp[i][j] <= X:
                current_min_fuel = min(current_min_fuel, dp[i][j])
                found = True
        
        if found:
            max_count = i
            min_fuel = current_min_fuel
            break
    
    if min_fuel == INF:
        print(f"0 0")
    else:
        print(f"{max_count} {min_fuel}")

solve()

第二题

给定一张n×m的网格图，每个网格可以是"空地"或者"障碍"，"空地"用.表示，"障碍"用X表示。