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 个整数,相邻的整数之间使用一个空格分隔,表示操作 完成后的序列。
输入样例
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;
}
原文地址: https://www.cveoy.top/t/topic/nanR 著作权归作者所有。请勿转载和采集!