题目描述

给定序列 (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 个整数,相邻的整数之间使用一个空格分隔,表示操作 完成后的序列。

输入样例

5 4
1 3
0 2
1 4
0 1

输出样例

1 4 3 2 5

算法1

(暴力枚举) $O(n*m)$

按照题意模拟即可

时间复杂度

$O(n*m)$

参考文献

C++ 代码

// 算法 1: 暴力枚举
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = i + 1;
    }
    for (int i = 0; i < m; i++) {
        int p, q;
        cin >> p >> q;
        if (p == 0) {
            sort(a.begin(), a.begin() + q, greater<int>());
        } else {
            sort(a.begin() + q - 1, a.end());
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }
    cout << endl;
    return 0;
}

算法2

(暴力枚举) $O(n*m)$

blablabla

时间复杂度

参考文献

C++ 代码

// 算法 2: 暴力枚举
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // ...
    return 0;
}
C++ 程序:序列操作 - 降序排列和升序排列

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

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