简答题
偏难
#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个正整数,代表多次升序排序后的序列。
输入样例
输出样例
第一次升序排序后,序列为[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] > 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区间范围内数据进行排序操作,调用之前定义好的排序方法
输出结果(注意每个元素用空格分割,且最后一个元素没有空格)