✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：小兰的图书整理方案

1️⃣：分离奇数和偶数序列，保持原始相对顺序

2️⃣：分别计算两个序列的最长严格递增子序列（LIS）长度

3️⃣：答案为两个LIS长度之和

难度：中等

这道题目的关键在于理解队列的FIFO特性和奇偶性限制，通过Dilworth定理将问题转化为求最长上升子序列。每个队列内必须严格递减才能保证最终输出的递减性，而最少的递减子序列数等于最长上升子序列的长度。

题目二：小毛的部门绩效优化

1️⃣：将权值公式拆解为行和与列和的线性组合

2️⃣：分别计算矩阵的行和与列和

3️⃣：使用贪心策略：大数配大数，分别排序后计算点积

难度：中等

这道题目的核心在于数学变形，将复杂的矩阵权值计算转化为两个独立的一维优化问题。通过排序后的贪心匹配，可以保证总权值最大化，体现了"同序配对使点积最大"的经典贪心思想。

题目三：小基的仓储选址优化

1️⃣：理解分段线性凸函数的性质

2️⃣：收集所有区间端点并排序

3️⃣：选择第n小的端点作为最优位置

难度：中等

这道题目是经典的几何中位数问题，关键在于理解每个区间对应的成本函数是分段线性的，总成本函数是凸函数。通过分析斜率变化，可以发现最优解就是所有端点的中位数，避免了复杂的数值优化。

01. 小兰的图书整理方案

问题描述

小兰是一名图书管理员，她负责整理图书馆的一批新书。这些新书有着不同的编号，需要按照编号从大到小的顺序重新排列上架。

小兰决定使用若干个临时书架来帮助整理这些图书。每个临时书架都按照先进先出的规则工作，即最先放入的书会最先被取出。整个整理过程分为两个阶段：

分配阶段：按照新书的原始顺序，小兰需要选择一个临时书架将每本书放入。但是有一个限制条件：如果临时书架中已经有书了，那么只能将编号奇偶性相同的书放入同一个书架。也就是说，奇数编号的书只能和奇数编号的书放在一起，偶数编号的书只能和偶数编号的书放在一起。

取出阶段：当所有书都分配完毕后，小兰开始从临时书架中取书上架。每一步，她可以选择任意一个临时书架，取出其顶部的书并放到最终的书架上。目标是让最终书架上的书按照编号严格从大到小的顺序排列。

显然，如果不限制临时书架的数量，这个任务很容易完成。所以你需要帮助小兰计算，至少需要多少个临时书架，才能完成上述整理流程并保证最终的书籍按编号严格递减排列。

输入格式

第一行包含一个正整数 （），表示图书的数量。

第二行包含 个整数 （），表示图书的编号序列。

输出格式

输出一个整数，表示至少需要多少个临时书架。

样例输入

9
8 4 2 5 3 7 1 6 0

4
1 2 3 4

样例输出

4

4

数据范围

题解

这道题本质上是一个贪心加动态规划的问题。关键在于理解题目的约束条件和最终目标。

首先分析问题的核心：我们需要将序列分成若干个子序列，每个子序列内的元素必须满足两个条件：

1. 奇偶性相同
2. 在原序列中的相对位置保持递减（这样才能保证最终输出时的递减性）

这样，问题就转化为：

• 将所有奇数元素组成的子序列，分解为最少的严格递减子序列
• 将所有偶数元素组成的子序列，分解为最少的严格递减子序列
• 答案是两者之和

根据 Dilworth 定理，将序列分解为最少递减子序列的数量，等于该序列中最长严格递增子序列的长度。

具体算法步骤：

1. 分别提取原序列中的奇数和偶数，保持相对顺序
2. 对奇数序列求最长严格递增子序列（LIS）的长度
3. 对偶数序列求最长严格递增子序列的长度
4. 两个长度相加就是答案

时间复杂度为 ，使用经典的 LIS 算法即可处理 的数据范围。

参考代码

• Python

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

def calc_lis(arr):
    """计算严格递增LIS的长度"""
    if not arr:
        return 0
    
    tail = []  # tail[i] 表示长度为i+1的递增序列的最小结尾值
    for x in arr:
        pos = bisect_left(tail, x)
        if pos == len(tail):
            tail.append(x)
        else:
            tail[pos] = x
    return len(tail)

# 读取输入
n = int(input())
a = list(map(int, input().split()))

# 分离奇数和偶数序列
odd_seq = []
even_seq = []

for x in a:
    if x % 2 == 1:
        odd_seq.append(x)
    else:
        even_seq.append(x)

# 计算两个序列的LIS长度并相加
result = calc_lis(odd_seq) + calc_lis(even_seq)
print(result)

• Cpp

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

// 计算严格递增LIS的长度
int get_lis_len(const vector<int>& arr) {
    if (arr.empty()) return 0;
    
    vector<int> tail; // tail[i]表示长度为i+1的递增序列的最小结尾值
    for (int x : arr) {
        auto pos = lower_bound(tail.begin(), tail.end(), x);
        if (pos == tail.end()) {
            tail.push_back(x);
        } else {
            *pos = x;
        }
    }
    return tail.size();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> odd_nums, even_nums;
    
    // 读取数据并分离奇偶数
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x & 1) {
            odd_nums.push_back(x);
        } else {
            even_nums.push_back(x);
        }
    }
    
    // 计算答案：两个LIS长度之和
    int ans = get_lis_len(odd_nums) + get_lis_len(even_nums);
    cout << ans << "\n";
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    // 计算严格递增LIS的长度
    public static int getLisLen(List<Integer> arr) {
        if (arr.isEmpty()) return 0;
        
        List<Integer> tail = new ArrayList<>();
        for (int x : arr) {
            int pos = Collections.binarySearch(tail, x);
            if (pos < 0) pos = -(pos + 1);
            
            if (pos == tail.size()) {
                tail.add(x);
            } else {
                tail.set(pos, x);
            }
        }
        return tail.size();
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        List<Integer> oddNums = new ArrayList<>();
        List<Integer> evenNums = new ArrayList<>();
        
        // 读取数据并分离奇偶数
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            if (x % 2 == 1) {
                oddNums.add(x);
            } else {
                evenNums.add(x);
            }
        }
        
        // 计算答案：两个LIS长度之和
        int result = getLisLen(oddNums) + getLisLen(evenNums);
        System.out.println(result);
    }
}

02. 小毛的部门绩效优化

问题描述

小毛是一家大型企业的人事总监，他负责管理公司的 个部门和 个项目。每个部门 都有一个基础权重 ，每个项目 都有一个难度系数 。

公司建立了一个 的绩效矩阵，其中第 个部门在第 个项目上的基础得分为 。

每个部门-项目组合的最终绩效评分计算公式为：

小毛可以对组织架构进行调整（但部门权重 和项目难度系数 保持不变）：

• 部门重组：交换任意两个部门的所有项目分配
• 项目调整：交换任意两个项目在所有部门中的分配

小毛希望通过这些调整，使得公司的总绩效评分达到最大值。

输入格式

第一行包含两个正整数 （），分别表示部门数量和项目数量。

第二行包含 个正整数 （），表示各部门的基础权重。

第三行包含 个正整数 （），表示各项目的难度系数。

接下来 行，每行包含 个正整数 （），表示绩效矩