简答题 偏难
#18215

区间排序 时间限制: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:python;toolbar:false">N = 1010 a = [0] * N n = 0 def bubbleSort(l, r): flag = True while flag: flag = False for i in range(l, r): if a[i] &gt; a[i + 1]: flag = True a[i], a[i + 1] = a[i + 1], a[i] n = int(input()) s = input().split() for i in range(1, n + 1): a[i] = int(s[i-1]) q = int(input()) while q: q -= 1 l, r = map(int, input().split()) bubbleSort(l, r) for i in range(1, n + 1): print(a[i], end=" " if i != n else "\n")</pre>
解析

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

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

处理部分:

存储输入数据

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

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

输出结果(注意每个元素用空格分割,且最后一个元素没有空格)