【GESP】C++四级真题 luogu-B4041 [GESP202409 四级] 区间排序
GESP C++四级2024年9月真题。本题主要考查排序和数组的应用。使用内置函数sort难度不大，整体难度⭐⭐★☆☆。本题在洛谷评定为普及-。
luogu-B4041 [GESP202409 四级] 区间排序
题目要求
题目描述
小杨有一个包含 $n$ 个正整数的序列 $a$。
小杨计划对序列进行多次升序排序，每次升序排序小杨会选择一个区间 $[l,r]$（$l \leq r$）并对区间内所有数字，即进行升序 $a_l, a_{l + 1}, \dots a_r$ 排序。每次升序排序会在上一次升序排序的结果上进行。
小杨想请你计算出多次升序排序后的序列。
输入格式
第一行包含一个正整数 $n$，含义如题面所示。 第二行包含 $n$ 个正整数 $a_1, a_2, \dots a_n$，代表序列 $a$。
第三行包含一个正整数 $q$，代表排序次数。
之后 $q$ 行，每行包含两个正整数 $l, r$，代表将区间 $[l_i, r_i]$ 内所有数字进行升序排序。
输出格式
输出一行包含 $n$ 个正整数，代表多次升序排序后的序列。
输入输出样例 #1
输入 #1
1
2
3
4
5
6
5
3 4 5 2 1
3
4 5
3 4
1 3
输出 #1
1
1 3 4 5 2
说明/提示
样例 1 解释
- 第一次升序排序后，序列为 $[3,4,5,1,2]$；
- 第二次升序排序后，序列为 $[3,4,1,5,2]$；
- 第三次升序排序后，序列为 $[1,3,4,5,2]$；
数据规模与约定
对于全部的测试数据，保证 $1 \leq n, a_i, q \leq 100$，$1 \leq l_i \leq r_i \leq n$。
题目分析
本题的解题思路如下：
- 题目要求对一个长度为 $n$ 的序列进行多次区间排序操作。每次操作会指定一个区间 $[l,r]$，将该区间内的数字升序排序。具体要求是：
- 每次排序都是在上一次排序结果的基础上进行
- 排序区间由左端点 $l$ 和右端点 $r$ 确定
- 区间内的数字需要按升序排列
- 解题关键点：
- 序列长度 $n$ 和排序次数 $q$ 都不超过 100，可以使用暴力方法
- 每次排序只影响指定区间内的数字，区间外的数字保持不变
- 需要按顺序执行所有排序操作，因为后面的排序基于前面排序的结果
- 具体实现步骤：
- 读入序列长度 $n$ 和初始序列
- 读入排序操作次数 $q$
- 循环处理每次排序操作：
- 读入区间范围 $[l,r]$
- 对区间内的数字进行升序排序
- 输出最终序列
- 时间复杂度分析：
- 每次排序操作的时间复杂度：$O(k\log k)$，其中 $k$ 是区间长度
- 总共进行 $q$ 次排序操作
- 由于 $n,q\leq100$，总时间复杂度约为 $O(q\cdot n\log n)$
- 数据规模较小，暴力方法完全可以通过
- 注意事项：
- 数组下标从 0 开始，而题目给出的区间范围从 1 开始，需要注意转换
- 使用
std::sort进行排序时，区间是左闭右开的 $[l,r)$ - 输出时数字之间要用空格分隔
这道题目是一道典型的模拟题，主要考察对数组和排序的基本操作。只要按照题目要求，依次执行每次排序操作即可。使用 C++ 标准库的 sort 函数可以很方便地实现区间排序。
关于sort的用法，前面文章【GESP】C++四级真题 luogu-B3851 [GESP202306 四级] 图像压缩已经介绍过。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
// 定义数组存储序列，由于n<=100，定义105大小足够
int num_ary[105];
int main() {
// 读入序列长度n
int n;
std::cin >> n;
// 读入n个正整数，存入数组
for (int i = 0; i < n; i++) {
std::cin >> num_ary[i];
}
// 读入排序操作次数q
int q;
std::cin >> q;
// 执行q次排序操作
for (int i = 0; i < q; i++) {
// 读入每次操作的区间范围[l,r]
int l, r;
std::cin >> l >> r;
// 使用std::sort对区间[l,r]进行升序排序
// 注意：数组下标从0开始，所以要减1
// sort的区间是左闭右开[first, last)，所以r不用减1
std::sort(num_ary + l - 1, num_ary + r);
}
// 输出最终序列
for (int i = 0; i < n; i++) {
std::cout << num_ary[i] << " ";
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
