A31061. 区间排序
填空题
较难
知识点
题目描述
区间排序
题目描述
小杨有一个包含n个正整数的序列a。
小杨计划对序列进行多次升序排序，每次升序排序小杨会选择一个区间[l,r]（l≤r）并对区间内所有数字，即al,al+1,,,ar进行升序排序。每次升序排序会在上一次升序排序的结果上进行。
小杨想请你计算出多次升序排序后的序列。
输入格式
第一行包含一个正整数n，含义如题目所示。
第二行包含n个正整数 ，al,al+1,,,an代表序列。
第三行包含一个正整数 ，代表排序次数。
之后q行，每行包含两个正整数li,ri，代表将区间[li,ri]内所有数字进行升序排序。
输出格式
输出一行包含n个正整数，代表多次升序排序后的序列。
样例1
输入
5
3 4 5 2 1
3
4 5
3 4
1 3
输出
1 3 4 5 2 1
第一次升序排序后，序列为[3,4,5,1,2]；
第二次升序排序后，序列为[3,4,1,5,2]；
第三次升序排序后，序列为[1,3,4,5,2]；
对于全部数据，保证有1≤n≤100,1≤ai≤100,1≤q≤100,1≤li≤ri≤n。
参考答案
#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";
}
}
上一题
下一题