✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

拼多多

题目一：藏书阁的珍稀字符收集

1️⃣：将所有残页中的字符收集并记录来源

2️⃣：按字典序排序字符，贪心选择满足条件的最小字符

难度：中等

这道题目的核心在于理解贪心策略的适用性。由于我们可以任意排列选出的字符，所以最优解就是按字典序从小到大选择字符，同时需要遵守每页残页的字符数量限制。时间复杂度为O(N log N)，其中N是总字符数。

题目二：明星合约优化问题

1️⃣：将明星片酬关系建模为有向图

2️⃣：通过拓扑排序和边松弛确定最小总片酬

难度：中等

这道题目的核心在于识别其图论模型，将片酬关系转化为有向图问题。通过拓扑排序可以检测是否存在环（无解的情况），同时在排序过程中进行边松弛操作确保满足所有关系约束。该方法的时间复杂度为O(n+m)，实现简洁高效。

题目三：露天音乐节地形优化

1️⃣：识别最少调整数量等于总位置数减去最长递增子序列长度

2️⃣：使用耐心排序算法高效计算最长递增子序列(LIS)

难度：中等

这道题目的关键在于转化思路：保留最长严格递增子序列，调整其余位置。由于调整后的高度可以为任意值，我们只需要找出可以保留的最大元素数量，即最长递增子序列的长度。使用耐心排序算法可以在O(n log n)时间内解决，适应题目的数据规模要求。

题目四：智能排序助手

1️⃣：扫描数列找到逆序对，在前缀中寻找最优交换元素

2️⃣：贪心选择大于x且值最小的元素进行交换，最小化操作次数

难度：中等偏难

这道题目考察对贪心策略的理解和实现。核心思想是在修正逆序对时，选择前缀中大于x且值最小的元素进行交换，这样能最大限度保留未来可能的交换机会。时间复杂度为O(n²)，适用于给定的数据范围。判断无解的情况也是关键点之一。

01. 藏书阁的珍稀字符收集

问题描述

小柯是一位独特的珍稀字符收藏家，她最近收到了一批古籍残页，每页上都有一些珍贵的古文字符。为了重现某段失传已久的古文，小柯需要从这些残页中收集并组合出一段长度为 的古文。

具体规则如下：

• 有 页残页，每页上有一串古文字符
• 小柯可以从第 页残页中最多取出 个字符
• 取出的字符可以按任意顺序重新排列组合
• 小柯希望组合出的古文字典序尽可能小

请帮助小柯确定最终能组合出的字典序最小的古文。

输入格式

第一行，两个整数 和 ，表示有 页残页以及目标古文的长度。

接下来 行，第 行有一个字符串和一个整数：。

是第 页残页上的字符串

是从第 页残页上最多可取出的字符个数

输出格式

一个字符串，表示字典序最小的古文。

样例输入

2 3
abb 2
ccaa 1

3 5
aaa 0
bab 2
aaa 3

样例输出

aab

aaaab

数据范围

• 
• 
• 
• 

样例 解释说明

样例1	从第2页残页中取出字符'a'，从第1页残页中取出字符'a'和'b'，拼接成"aab"的字典序最小。
样例2	从第3页残页中取出所有字符'aaa'，从第2页残页中取出字符'ab'，拼接成"aaaab"的字典序最小。

题解

这道题目看起来有点复杂，但其实有一个很直观的策略可以得到字典序最小的古文。

首先我们来思考：如果要让组合出的字符串字典序尽可能小，那么应该优先选择什么字符呢？显然是字典序小的字符，比如'a'要优先于'b'。

解题思路如下：

1. 将所有残页中的字符集中起来，但记录每个字符来自哪一页残页
2. 按照字符的字典序（即ASCII码）从小到大排序
3. 按顺序遍历排序后的字符集，贪心地选择当前字符序最小的字符
4. 在选择时，需要遵守每页残页最多取 个字符的限制
5. 一旦选够了 个字符，就可以停止选择

为什么这个贪心策略是正确的？因为我们可以任意排列选出的字符，所以最优策略就是按字典序从小到大选择，同时遵守每页的取字符数限制。

时间复杂度分析：

• 收集所有字符需要 O(总字符数)
• 排序需要 O(总字符数 × log(总字符数))
• 遍历选择需要 O(总字符数)

由于总字符数最多为所有残页字符数之和，即 ，而这个值不超过1,000,000，所以算法的总时间复杂度为 O(N × log(N))，其中N是总字符数。这在给定的数据范围内是可以接受的。

参考代码

• Python

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

# 读取输入
n, k = map(int, input().split())
src = []  # 用于存储每个字符及其来源

# 收集所有字符
limits = []
for i in range(n):
    s, x = input().split()
    x = int(x)
    limits.append(x)
    # 记录每个字符及其来源页码
    for c in s:
        src.append((c, i))

# 按字符字典序排序
src.sort()

# 记录每页已选择的字符数
cnt = [0] * n
res = []

# 贪心选择字典序最小的字符
for c, idx in src:
    if len(res) == k:
        break
    # 检查是否可以从该页再取字符
    if cnt[idx] < limits[idx]:
        cnt[idx] += 1
        res.append(c)

# 输出结果
print(''.join(res)) 

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    
    // 用于存储每个字符及其来源
    vector<pair<char, int>> chars;
    vector<int> limits(n);
    
    // 收集所有字符
    for (int i = 0; i < n; i++) {
        string s;
        int x;
        cin >> s >> x;
        limits[i] = x;
        
        // 记录字符和来源页码
        for (char c : s) {
            chars.emplace_back(c, i);
        }
    }
    
    // 按字典序排序
    sort(chars.begin(), chars.end());
    
    // 记录每页已选择的字符数
    vector<int> used(n, 0);
    string result;
    
    // 贪心选择字典序最小的字符
    for (auto [c, idx] : chars) {
        if (result.size() == k) break;
        
        if (used[idx] < limits[idx]) {
            used[idx]++;
            result.push_back(c);
        }
    }
    
    cout << result << "\n";
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 读取输入
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        List<Pair> chars = new ArrayList<>();
        int[] limits = new int[n];
        
        // 收集所有字符
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            int x = Integer.parseInt(st.nextToken());
            limits[i] = x;
            
            // 记录字符和来源页码
            for (char c : s.toCharArray()) {
                chars.add(new Pair(c, i));
            }
        }
        
        // 按字典序排序
        Collections.sort(chars);
        
        // 记录每页已选择的字符数
        int[] used = new int[n];
        StringBuilder result = new StringBuilder();
        
        // 贪心选择字典序最小的字符
        for (Pair p : chars) {
            if (result.length() == k) break;
            
            if (used[p.idx] < limits[p.idx]) {
                used[p.idx]++;
                result.append(p.c);
            }
        }
        
        System.out.println(result.toString());
    }
    
    static class Pair implements Comparable<Pair> {
        char c;
        int idx;
        
        Pair(char c, int idx) {
            this.c = c;
            this.idx = idx;
        }
        
        @Override
        public int compareTo(Pair other) {
            return Character.compare(this.c, other.c);
        }
    }
}

02. 明星合约优化问题

问题描述

小基娱乐公司正在筹备一部新的综艺节目，需要签约多位明星参与录制。为了确保节目顺利进行，公司需要合理安排每位明星的片酬，避免因片酬不公引起的明星罢录。

公司的节目策划组负责制定片酬方案，每位策划都有自己的意见。在讨论中，策划们会对明星片酬提出相对关系建议，例如"明星A的片酬应该高于明星B的片酬"，这些意见以明确的优先顺序对表示。

公司规定每位明星的基本片酬至少为100元，且每次调整片酬的增量为10元。在满足所有策划意见的前提下，公司希望明星的总片酬尽可能低。

请你帮助小基娱乐公司计算：在满足所有策划意见的条件下，明星片酬总额的最小值是多少？

输入格式

第一行为一个整数 ，表示共有 个测试数据。

每组测试数据:

第一行为两个整数 和 ，分别表示签约明星的总数和策划提出的意见数。

接下来的 行:

每行输入两个整数 表示有策划认为明星 的片酬应当比明星 的片酬高。

输出格式

每组数据输出一个结果，每个结果占一行，如果满足不了所有策划的意见则输出 。

样例输入

1
7 4
7 2
4 6
2 5
7 5

1
3 2
1 3
3 2

样例输出

740

330

数据范围

• 对于 % 的数据有:
• 对于 % 的数据有:
• 对于 % 的数据有:

样例 解释说明

样例1	明星7的片酬需要比明星2和明星5高，明星4的片酬需要比明星6高，明星2的片酬需要比明星5高。最小总片酬方案为：明星1(100元)、明星2(110元)、明星3(100元)、明星4(110元)、明星5(100元)、明星6(100元)、明星7(120元)，总计740元。
样例2	明星1的片酬需要比明星3高，明星3的片酬需要比明星2高。最小总片酬方案为：明星1(120元)、明星2(100元)、明星3(110元)，总计330元。

题解

这道题目本质上是一个有向图问题，我们可以将策划的意见视为有向图的边，然后使用图算法来解决。

解题思路

1. 首先，策划的每个意见"明星a的片酬应该高于明星b的片酬"可以看作是明星b到明星a的一条有向边。这表示a的片酬至少要比b高10元（题目中的增量单位）。

2. 我们的任务是给每个明星分配片酬，使得所有这些关系都满足，并且总片酬最小。这实际上是在一个有向图上求解一个最短路径问题的变种。

3. 我们可以使用拓扑排序算法：

   • 初始化每个明星的片酬为基本值100元（或者用10单位表示）
   • 按照拓扑顺序处理每个明星
   • 对于每条边(b,a)，更新a的片酬为max(a的当前片酬, b的片酬+1)

4. 如果图中存在环，那么意味着有矛盾的意见（比如a>b>c>a），此时输出-1

5. 否则，输出所有明星最终片酬的总和

为什么这个方法有效？

• 拓扑排序确保我们按照依赖关系处理节点
• 每次松弛操作保证了片酬差至少为10元
• 由于我们总是取最大值，这确保了所有关系都能被满足
• 因为我们是从初始最小值开始增加，最终得到的总和就是满足所有条件的最小可能值

时间复杂度分析

• 构建图和初始化：O(n+m)
• 拓扑排序和处理：O(n+m)

总时间复杂度为O(n+m)，这对于题目给出的数据范围（n≤10000，m≤20000）是完全可接受的。

参考代码

• Python

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

def solve():
    # 读取输入
    n, m = map(int, input().split())
    
    # 构建图
    graph = [[] for _ in range(n+1)]
    in_deg = [0] * (n+1)
    
    for _ in range(m):
        a, b = map(int, input().split())
        # a的片酬要比b高，即a依赖于b
        graph[b].append(a)
        in_deg[a] += 1
    
    # 初始化片酬（以10为单位）
    fee = [10] * (n+1)  # 每个明星至少100元
    
    # 拓扑排序
    q = deque()
    for i in range(1, n+1):
        if in_deg[i] == 0:
            q.append(i)
    
    cnt = 0  # 记录处理的节点数
    while q:
        u = q.popleft()
        cnt += 1
        
        # 更新邻居节点
        for v in graph[u]:
            # v的片酬至少比u高10元
            fee[v] = max(fee[v], fee[u] + 1)
            in_deg[v] -= 1
            if in_deg[v] == 0:
                q.append(v)
    
    # 检查是否存在环
    if cnt < n:
        return -1
    
    # 计算总片酬
    total = sum(fee[1:]) * 10
    return total

# 主函数
t = int(input())
for _ in range(t):
    print(solve())

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        // 构建图
        vector<vector<int>> graph(n+1);
        vector<int> in_deg(n+1, 0);
        
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            // a的片酬要比b高，即边b->a
            graph[b].push_back(a);
            in_deg[a]++;
        }
        
        // 初始化片酬（以10为单位）
        vector<int> fee(n+1, 10);  // 每个明星至少100元
        
        // 拓扑排序
        queue<int> q;
        for (int i = 1; i <= n; i++) {
            if (in_deg[i] == 0) {
                q.push(i);
            }
        }
        
        int cnt = 0;  // 记录处理的节点数
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            cnt++;
            
            // 更新邻居节点
            for (int v : graph[u]) {
                // v的片酬至少比u高10元
                fee[v] = max(fee[v], fee[u] + 1);
                if (--in_deg[v] == 0) {
                    q.push(v);
                }
            }
        }
        
        // 检查是否存在环
        if (cnt < n) {
            cout << -1 << "