✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

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

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

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

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

滴滴

题目一：小兰的音响调试

1️⃣：使用动态规划处理0-1背包问题，通过偏移避免负数索引

2️⃣：根据音量调节效果的正负性选择不同的遍历方向

3️⃣：利用前缀和优化状态转移，找到最小费用方案

难度：中等

这道题目本质上是一个带约束的0-1背包问题，关键在于将音量值进行偏移处理来避免负数索引。通过动态规划求解使总音量调节效果恰好为1的最小费用方案，需要掌握背包问题的状态转移和边界处理技巧。

题目二：小毛的画廊展品调整

1️⃣：理解调配过程的本质，将问题转化为二分搜索

2️⃣：分别二分最大的最小值和最小的最大值

3️⃣：使用前缀和快速计算调配操作的需求次数

难度：中等偏难

这道题目需要深入理解调配过程对数据分布的影响，通过数学分析将模拟问题转化为二分搜索问题。关键在于设计高效的可行性判断函数，利用前缀和优化计算复杂度，实现对大数据量的快速处理。

01. 小兰的音响调试

小兰是一位资深的音响工程师，她接到了一个为音乐会调试音响设备的任务。音乐会现场有 种不同的音响设备可供选择，每种设备都有其独特的音效特性。

有些设备能够增强音量（提供正的音量值），而另一些则会降低整体音量（提供负的音量值，表示吸音或降噪功能）。每种设备最多只能使用一台，并且租用每种设备都需要支付一定的费用。

根据音乐会的特殊要求，小兰需要将最终的音量调节到恰好为 个单位，这样才能获得完美的音效平衡。现在请你帮助小兰计算，在达到这个音效要求的前提下，最少需要花费多少租用费用。

问题描述

小兰有 种音响设备可供选择，第 种设备能够提供 的音量调节效果（正数表示增强音量，负数表示降低音量），租用费用为 。小兰需要选择若干设备，使得总的音量调节效果恰好为 ，并且总租用费用最小。

输入格式

第一行包含一个正整数 （），表示可选择的音响设备数量。

接下来 行，每行包含两个整数 ，表示第 种设备的音量调节效果和租用费用。

其中 ，，且所有 之和的绝对值不超过 。

输出格式

如果无法使总音量调节效果恰好为 ，则输出 。

如果可以达到要求，则输出所需的最小租用费用。

样例输入

4
8 1
-4 2
-2 3
-1 4

2
6 3
-2 2

样例输出

10

-1

样例	解释说明
样例1	选择第1种设备（音量+8，费用1）和第2、3种设备（音量-4-2=-6，费用2+3=5），总音量为8-6=2，不满足要求。正确方案是选择第1种设备和第3、4种设备，总音量为8-2-1=5，仍不为1。实际上选择第1、2、3种设备，总音量为8-4-2=2，再加第4种设备变为8-4-2-1=1，总费用为1+2+3+4=10。
样例2	无论怎么选择设备，都无法使总音量调节效果恰好为1

数据范围

• 
• 
• 
• 

题解

这道题本质上是一个带约束的0-1背包问题。我们需要选择一些设备，使得它们的音量调节效果之和恰好为1，并且总费用最小。

关键思路是将音量值进行偏移处理，避免处理负数索引。因为所有 之和的绝对值不超过6000，所以音量调节效果的范围在 之间。我们可以将所有值偏移6000，这样就能用数组索引来表示不同的音量值了。

具体步骤：

1. 状态定义：设 表示音量调节效果为 时的最小费用
2. 初始化：（音量为0的基础状态），其余为无穷大
3. 状态转移：对于每个设备 ，根据 的正负性决定遍历方向
   • 若 ：逆序遍历避免重复使用
   • 若 ：正序遍历避免重复使用
4. 答案获取：检查 （对应音量为1）的值

时间复杂度为 ，空间复杂度相同，对于给定的数据规模完全可行。

参考代码

• Python

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

n = int(input())
offset = 6000
range_size = offset * 2 + 1
dp = [float('inf')] * range_size
dp[offset] = 0

for _ in range(n):
    a, b = map(int, input().split())
    if a >= 0:
        # 正向贡献，逆序遍历避免重复使用
        for s in range(range_size - 1 - a, -1, -1):
            if dp[s] != float('inf'):
                dp[s + a] = min(dp[s + a], dp[s] + b)
    else:
        # 负向贡献，正序遍历避免重复使用  
        for s in range(-a, range_size):
            if dp[s] != float('inf'):
                dp[s + a] = min(dp[s + a], dp[s] + b)

ans = dp[offset + 1] if offset + 1 < range_size else float('inf')
print(-1 if ans == float('inf') else ans)

• Cpp

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

const long long INF = 4e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    const int off = 6000;           // 偏移量，保证下标非负
    const int rng = off * 2 + 1;    // 范围：-6000 到 6000
    vector<long long> dp(rng, INF);
    dp[off] = 0;                    // 音量为0的初始状态
    
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        
        if (a >= 0) {
            // 正向贡献，逆序遍历
            for (int s = rng - 1 - a; s >= 0; --s) {
                if (dp[s] != INF) {
                    dp[s + a] = min(dp[s + a], dp[s] + b);
                }
            }
        } else {
            // 负向贡献，正序遍历
            for (int s = -a; s < rng; ++s) {
                if (dp[s] != INF) {
                    dp[s + a] = min(dp[s + a], dp[s] + b);
                }
            }
        }
    }
    
    long long ans = (off + 1 < rng) ? dp[off + 1] : INF;
    cout << (ans == INF ? -1 : ans) << "\n";
    
    return 0;
}

• Java

import java.util.*;
import java.io.*;

public class Main {
    static final long INF = (long) 4e18;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        final int offset = 6000;           // 偏移量
        final int range = offset * 2 + 1;  // 范围大小
        long[] dp = new long[range];
        Arrays.fill(dp, INF);
        dp[offset] = 0;                    // 初始状态：音量为0
        
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int b = Integer.parseInt(line[1]);