✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：图书馆整理计划

1️⃣：贪心策略从左到右固定每个位置的最优元素

2️⃣：使用线段树维护区间最小值信息，支持单点更新和区间查询

3️⃣：每次选择后缀中的最小值交换到当前位置

难度：中等

这道题目的核心是贪心思想，通过每次将后缀区间的最小值移动到当前位置来保证字典序最小。线段树的使用使得我们能够高效地进行区间最值查询和单点更新，时间复杂度为 O(n log n)。

题目二：花园景观设计

1️⃣：将圆环问题转化为线性问题，通过数组扩展处理

2️⃣：利用前缀和技巧计算正向和反向建造成本

3️⃣：数学推导得出反向成本公式，避免重复计算

难度：中等

这道题目巧妙地结合了圆环数据结构和前缀和优化。关键insight是发现反向建造成本可以通过数学公式快速计算，避免了枚举所有建造顺序的复杂度。

题目三：学生影响力评估

1️⃣：通过代数变换简化影响关系条件

2️⃣：将问题转化为区间最大值及其出现次数的查询

3️⃣：使用线段树维护区间最值信息

难度：中等偏难

这道题目需要深入理解影响关系的数学本质，通过转换将复杂的图论问题简化为区间查询问题。线段树的应用使得我们能够高效地处理多次查询，实现 O((n+q) log n) 的时间复杂度。

01. 图书馆整理计划

问题描述

小兰是图书馆的管理员，她面临着一个棘手的图书整理任务。图书馆的一个书架上有 本书，这些书的编号恰好是 到 的一个排列，但由于读者的随意摆放，书籍的顺序变得杂乱无章。

小兰希望将这些书按照编号从小到大的顺序重新排列，但由于时间限制，她最多只能进行 次交换操作。每次操作可以选择任意两本书进行位置交换。

现在小兰想知道，在有限的交换次数内，她能够得到的字典序最小的书籍排列是什么？

输入格式

每个测试文件均包含多组测试数据。

第一行包含一个正整数 ()，表示测试数据的组数。

对于每组测试数据：

第一行包含两个正整数 (, )，分别表示书籍的数量和最多可以进行的交换次数。

第二行包含 个正整数 ()，表示当前书架上书籍的编号排列，保证是 到 的一个排列。

保证所有测试数据中 的总和不超过 。

输出格式

对于每组测试数据，输出一行 个整数，表示经过至多 次交换操作后能够得到的字典序最小的排列。

样例输入

2
2 1
2 1
3 4
3 2 1

样例输出

1 2
1 2 3

数据范围

• 
• 
• 
• 
• 保证所有测试数据中 的总和不超过

题解

这道题的核心思想是贪心策略。每次交换操作可以将后缀区间中的任意元素移动到当前位置，所以为了得到字典序最小的排列，应该从左到右依次固定每个位置上的最优元素。

具体做法是：从左到右遍历每个位置，如果当前位置右侧（包括当前位置）存在更小的元素，就将最小的那个元素交换到当前位置。这样可以保证每一步都让排列在字典序意义下变得更优。

为了高效地找到区间中的最小值及其位置，可以使用线段树来维护区间最小值信息。线段树支持单点更新和区间查询，时间复杂度为 。

总的时间复杂度为 ，对于给定的数据范围完全可以接受。

参考代码

• Python

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

class SegTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [(0, 0)] * (4 * self.n)  # (value, index)
        self.build(1, 0, self.n - 1, arr)
    
    def build(self, node, l, r, arr):
        if l == r:
            self.tree[node] = (arr[l], l)
            return
        mid = (l + r) // 2
        self.build(2 * node, l, mid, arr)
        self.build(2 * node + 1, mid + 1, r, arr)
        # 合并左右子树的结果，选择值更小的，如果值相等则选择下标更小的
        left_val, left_idx = self.tree[2 * node]
        right_val, right_idx = self.tree[2 * node + 1]
        if left_val < right_val or (left_val == right_val and left_idx < right_idx):
            self.tree[node] = (left_val, left_idx)
        else:
            self.tree[node] = (right_val, right_idx)
    
    def query(self, node, l, r, ql, qr):
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        res_val, res_idx = float('inf'), float('inf')
        
        if ql <= mid:
            val, idx = self.query(2 * node, l, mid, ql, qr)
            if val < res_val or (val == res_val and idx < res_idx):
                res_val, res_idx = val, idx
        if qr > mid:
            val, idx = self.query(2 * node + 1, mid + 1, r, ql, qr)
            if val < res_val or (val == res_val and idx < res_idx):
                res_val, res_idx = val, idx
        
        return res_val, res_idx
    
    def update(self, node, l, r, pos, val):
        if l == r:
            self.tree[node] = (val, pos)
            return
        mid = (l + r) // 2
        if pos <= mid:
            self.update(2 * node, l, mid, pos, val)
        else:
            self.update(2 * node + 1, mid + 1, r, pos, val)
        
        # 更新当前节点
        left_val, left_idx = self.tree[2 * node]
        right_val, right_idx = self.tree[2 * node + 1]
        if left_val < right_val or (left_val == right_val and left_idx < right_idx):
            self.tree[node] = (left_val, left_idx)
        else:
            self.tree[node] = (right_val, right_idx)

def solve():
    n, m = map(int, input().split())
    books = list(map(int, input().split()))
    
    # 构建线段树
    seg = SegTree(books)
    
    # 贪心地从左到右固定每个位置
    for i in range(n):
        if m == 0:
            break
        
        # 查找从位置i到末尾的最小值
        min_val, min_pos = seg.query(1, 0, n - 1, i, n - 1)
        
        # 如果当前位置不是最小值，则进行交换
        if min_val < books[i]:
            books[i], books[min_pos] = books[min_pos], books[i]
            # 更新线段树
            seg.update(1, 0, n - 1, i, books[i])
            seg.update(1, 0, n - 1, min_pos, books[min_pos])
            m -= 1
    
    return ' '.join(map(str, books))

T = int(input())
for _ in range(T):
    print(solve())

• Cpp

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

struct SegNode {
    int val, idx;
    SegNode(int v = INT_MAX, int i = INT_MAX) : val(v), idx(i) {}
    bool operator<(const SegNode& other) const {
        return val < other.val || (val == other.val && idx < other.idx);
    }
};

class SegTree {
private:
    int sz;
    vector<SegNode> tree;
    
    void build(int v, int tl, int tr, const vector<int>& arr) {
        if (tl == tr) {
            tree[v] = SegNode(arr[tl], tl);
        } else {
            int tm = (tl + tr) / 2;
            build(2*v, tl, tm, arr);
            build(2*v+1, tm+1, tr, arr);
            tree[v] = min(tree[2*v], tree[2*v+1]);
        }
    }
    
    void update(int v, int tl, int tr, int pos, int val) {
        if (tl == tr) {
            tree[v] = SegNode(val, pos);
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm)
                update(2*v, tl, tm, pos, val);
            else
                update(2*v+1, tm+1, tr, pos, val);
            tree[v] = min(tree[2*v], tree[2*v+1]);
        }
    }
    
    SegNode query(int v, int tl, int tr, int l, int r) {
        if (l > r) return SegNode();
        if (l == tl && r == tr) return tree[v];
        int tm = (tl + tr) / 2;
        return min(query(2*v, tl, tm, l, min(r, tm)),
                   query(2*v+1, tm+1, tr, max(l, tm+1), r));
    }
    
public:
    SegTree(const vector<int>& arr) : sz(arr.size()) {
        tree.resize(4 * sz);
        build(1, 0, sz-1, arr);
    }
    
    void update(int pos, int val) {
        update(1, 0, sz-1, pos, val);
    }
    
    SegNode query(int l, int r) {
        return query(1, 0, sz-1, l, r);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        vector<int> books(n);
        for (int i = 0; i < n; i++) {
            cin >> books[i];
        }
        
        SegTree seg(books);
        
        // 贪心地从左到右处理每个位置
        for (int i = 0; i < n && m > 0; i++) {
            SegNode min_node = seg.query(i, n-1);
            
            // 如果找到的最小值比当前位置的值小，进行交换
            if (min_node.val < books[i]) {
                swap(books[i], books[min_node.idx]);
                seg.update(i, books[i]);
                seg.update(min_node.idx, books[min_node.idx]);
                m--;
            }
        }
        
        // 输出结果
        for (int i = 0; i < n; i++) {
            if (i > 0) cout << " ";
            cout << books[i];
        }
        cout << "\n";
    }
    
    return 0;
}

• Java

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

public class Main {
    static class SegNode {
        int val, idx;
        
        SegNode(int val, int idx) {
            this.val = val;
            this.idx = idx;
        }
        
        boolean isLess(SegNode other) {
            return val < other.val || (val == other.val && idx < other.idx);
        }
    }
    
    static class SegTree {
        private int size;
        private SegNode[] tree;
        
        SegTree(int[] arr) {
            size = arr.length;
            tree = new SegNode[4 * size];
            build(1, 0, size - 1, arr);
        }
        
        private void build(int v, int tl, int tr, int[] arr) {
            if (tl == tr) {
                tree[v] = new SegNode(arr[tl], tl);
            } else {
                int tm = (tl + tr) / 2;
                build(2 * v, tl, tm, arr);
                build(2 * v + 1, tm + 1, tr, arr);
                tree[v] = min(tree[2 * v], tree[2 * v + 1]);
            }
        }
        
        void update(int pos, int val) {
            update(1, 0, size - 1, pos, val);
        }
        
        private void update(int v, int tl, int tr, int pos, int val) {
            if (tl == tr) {
                tree[v] = new SegNode(val, pos);
            } else {
                int tm = (tl + tr) / 2;
                if (pos <= tm) {
                    update(2 * v, tl, tm, pos, val);
                } else {
                    update(2 * v + 1, tm + 1, tr, pos, val);
                }
                tree[v] = min(tree[2 * v], tree[2 * v + 1]);
            }
        }
        
        SegNode query(int l, int r) {
            return query(1, 0, size - 1, l, r);
        }
        
        private SegNode query(int v, int tl, int tr, int l, int r) {
            if (l > r) return new SegNode(Integer.MAX_VALUE, Integer.MAX_VALUE);
            if (l == tl && r == tr) return tree[v];
            int tm = (tl + tr) / 2;
            return min(query(2 * v, tl, tm, l, Math.min(r, tm)),
                      query(2 * v + 1, tm + 1, tr, Math.max(l, tm + 1), r));
        }
        
        private SegNode min(SegNode a, SegNode b) {
            return a.isLess(b) ? a : b;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWrit