GESP202409 四级] 区间排序

屈老师

[GESP202409 四级] 区间排序

题目描述

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

小杨计划对序列进行多次升序排序，每次升序排序小杨会选择一个区间 $[l,r]$（$l \leq r$）并对区间内所有数字，即进行升序$a_l, a_{l + 1}, \dots a_r$ 排序。每次升序排序会在上一次升序排序的结果上进行。

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

1 3 4 5 2

提示

样例 1 解释

第一次升序排序后，序列为 $[3,4,5,1,2]$；
第二次升序排序后，序列为 $[3,4,1,5,2]$；
第三次升序排序后，序列为 $[1,3,4,5,2]$；

数据规模与约定

对于全部的测试数据，保证 $1 \leq n, a_i, q \leq 100$，$1 \leq l_i \leq r_i \leq n$。

#include<iostream>
#include<vector>
using namespace std;

vector<int> mao_sort(vector<int> lie,int end,int begin) {
	end = end - 1;
	begin = begin - 1;
	for (int i = 0; i < end-begin; i++)
	{
		for (int j = begin; j <= end-1-i ; j++)
		{
			if (lie[j]>lie[j+1])
			{
				int tem = lie[j];
				lie[j] = lie[j + 1];
				lie[j + 1] = tem;

			}
		}
	}
	return lie;
}
 
int main() {

	int n;
	vector<int> lie;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int temp;
		cin >> temp;
		lie.push_back(temp);
	}

	int num;
	cin >> num;
	for (int i = 0; i < num; i++)
	{
		int l, r;
		cin >> l >> r;
		lie = mao_sort(lie, r, l);
	}

	for (int i = 0; i < n; i++)
	{
		cout << lie[i]<<" ";
	}


	return 0;
}

屈老师

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void sort_intervals(vector<int>& arr, vector<pair<int, int>>& intervals) {
    for (auto& interval : intervals) {
        int start = interval.first;
        int end = interval.second;
        sort(arr.begin() + start-1, arr.begin() + end);
    }
}

int main() {
    int n; // 序列中的整数数量
    cin >> n;

    vector<int> arr(n); // 读取初始序列
    for (auto& x : arr) {
        cin >> x;
    }

    int m; // 排序操作的数量
    cin >> m;

    vector<pair<int, int>> intervals(m);
    for (auto& interval : intervals) {
        int first, second;
        cin >> interval.first >> interval.second;
    }

    sort_intervals(arr, intervals);

    for (auto& x : arr) {
        cout << x << " ";
    }

    return 0;
}