4645: 【GESP2409四级】区间排序

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

⼩杨有⼀个包含$n$ 个正整数的序列$a_i$ 。
小杨计划对序列进行多次升序排序，每次升序排序小杨会选择一个区间[$l$,$r$]（$l\le r$ ）并对区间内所有数字，即$a_l,a_{l+1},...,a_r$进行升序排序。每次升序排序会在上一次升序排序的结果上进行。
小杨想请你计算出多次升序排序后的序列。

输入

第一行包含一个正整数$n$ ，含义如题面所示。
第二行包含$n$ 个正整数$a_1,a_2,...,a_n$ ，代表序列。
第三行包含一个正整数$q$ ，代表排序次数。
之后$q$ 行，每行包含两个正整数$l_i$ ，$r_i$ ，代表将区间[$l_i$,$r_i$] 内所有数字进行升序排序。

输出

输出一行包含$n$ 个正整数，代表多次升序排序后的序列。

样例输入 复制 

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

样例输出 复制 

1 3 4 5 2

提示

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int n;
void bubbleSort(int l, int r) {
    bool flag = true;
    while (flag) {
        flag = false;
        for (int i = l; i < r; ++i) {
            if (a[i] > a[i + 1]) {
                flag = true;
                swap(a[i], a[i + 1]);
            }
        }
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        bubbleSort(l, r);
    }
    for (int i = 1; i <= n; i++) {
        cout << a[i];
        if (i != n) cout << " ";
        else cout << "\n";
    }
}

来源/分类

提交提交记录统计露一手!