C++ 实现序列排序操作:降序排列和升序排列
C++ 实现序列排序操作:降序排列和升序排列
问题描述
给定序列 (a1, a2, · · · , an) = (1, 2, · · · , n),即 ai = i。 小蓝将对这个序列进行 m 次操作,每次可能是将 a1, a2, · · · , aqi 降序排列, 或者将 aqi, aqi+1, · · · , an 升序排列。 请求出操作完成后的序列。
输入格式
输入的第一行包含两个整数 n, m,分别表示序列的长度和操作次数。 接下来 m 行描述对序列的操作,其中第 i 行包含两个整数 pi, qi 表示操作 类型和参数。当 pi = 0 时,表示将 a1, a2, · · · , aqi 降序排列;当 pi = 1 时,表示 将 aqi, aqi+1, · · · , an 升序排列。
输出格式
输出一行,包含 n 个整数,相邻的整数之间使用一个空格分隔,表示操作 完成后的序列。
思路
我们可以先将序列初始化为 (1, 2, · · · , n),然后模拟每次操作。对于降序排列操作,我们可以直接使用 sort 函数进行排序;对于升序排列操作,我们需要手动实现一个排序函数,将 aqi 到 an 这一段进行升序排序。
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
void ascending_sort(int* arr, int start, int end) {
for (int i = start; i < end; i++) {
for (int j = i + 1; j <= end; j++) {
if (arr[i] > arr[j]) {
swap(arr[i], arr[j]);
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
int* arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i + 1;
}
while (m--) {
int p, q;
cin >> p >> q;
if (p == 0) {
sort(arr, arr + q);
reverse(arr, arr + q);
} else {
ascending_sort(arr, q - 1, n - 1);
}
}
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
原文地址: https://www.cveoy.top/t/topic/napo 著作权归作者所有。请勿转载和采集!