【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

5
3 4 5 2 1
3
4 5
3 4
1 3

输出 #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$。

题目分析

本题的解题思路如下：

1. 题目要求对一个长度为 $n$ 的序列进行多次区间排序操作。每次操作会指定一个区间 $[l,r]$，将该区间内的数字升序排序。具体要求是：

   • 每次排序都是在上一次排序结果的基础上进行
   • 排序区间由左端点 $l$ 和右端点 $r$ 确定
   • 区间内的数字需要按升序排列

2. 解题关键点：

   • 序列长度 $n$ 和排序次数 $q$ 都不超过 100，可以使用暴力方法
   • 每次排序只影响指定区间内的数字，区间外的数字保持不变
   • 需要按顺序执行所有排序操作，因为后面的排序基于前面排序的结果

3. 具体实现步骤：

   • 读入序列长度 $n$ 和初始序列
   • 读入排序操作次数 $q$
   • 循环处理每次排序操作：
     • 读入区间范围 $[l,r]$
     • 对区间内的数字进行升序排序
   • 输出最终序列

4. 时间复杂度分析：

   • 每次排序操作的时间复杂度：$O(k\log k)$，其中 $k$ 是区间长度
   • 总共进行 $q$ 次排序操作
   • 由于 $n,q\leq100$，总时间复杂度约为 $O(q\cdot n\log n)$
   • 数据规模较小，暴力方法完全可以通过

5. 注意事项：

   • 数组下标从 0 开始，而题目给出的区间范围从 1 开始，需要注意转换
   • 使用 std::sort 进行排序时，区间是左闭右开的 $[l,r)$
   • 输出时数字之间要用空格分隔

这道题目是一道典型的模拟题，主要考察对数组和排序的基本操作。只要按照题目要求，依次执行每次排序操作即可。使用 C++ 标准库的 sort 函数可以很方便地实现区间排序。

关于sort的用法，前面文章【GESP】C++四级真题 luogu-B3851 [GESP202306 四级] 图像压缩已经介绍过。

示例代码

#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;
}