简答题 偏难
#20943

区间排序 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有一个包含n个正整数的序列a。 小杨计划对序列进行多次升序排序,每次升序排序小杨会选择…

区间排序

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一个包含n个正整数的序列a。

小杨计划对序列进行多次升序排序,每次升序排序小杨会选择一个区间[l,r](l≤r) 并对区间内所有数字,即al,al+1,...,ar进行升序排序。每次升序排序会在上一次升序排序的结果上进行。

小杨想请你计算出多次升序排序后的序列。

输入格式

第一行包含一个正整数n,含义如题面所示。

第二行包含n个正整数 a1,a2,...,an,代表序列。

第三行包含一个正整数q,代表排序次数。

之后q行,每行包含两个正整数li,ri,代表将区间[li,ri] 内所有数字进行升序排序。 ,

输出格式

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

输入样例

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

输出样例

1 3 4 5 2


第一次升序排序后,序列为[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。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; 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 &lt;r; ++i) { if (a[i] &gt; a[i + 1]) { flag = true; swap(a[i],a[i+1]); } } } } int main(){ cin&gt;&gt;n; for(int i=1;i&lt;=n;i++){ cin&gt;&gt;a[i]; } int q; cin&gt;&gt;q; while(q--){ int l,r; cin&gt;&gt;l&gt;&gt;r; bubbleSort(l,r); } for(int i=1;i&lt;=n;i++){ cout&lt;&lt;a[i]; if(i!=n)cout&lt;&lt;" "; else cout&lt;&lt;"\n"; } }</pre>
解析

将要排序的数据存储在列表中,初始化定义一个长度为1010的数组,尽可能大的数据,确保在输入规模较大的情况下不会越界

定义排序方法对数据进行排序

处理部分:

存储输入数据

处理需要进行排序的区间操作数q

对选定的l,r区间范围内数据进行排序操作,调用之前定义好的排序方法输出结果