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;
}
C++ 实现序列排序操作:降序排列和升序排列

原文地址: https://www.cveoy.top/t/topic/napo 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录