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 个整数,相邻的整数之间使用一个空格分隔,表示操作完成后的序列。
输入样例
10 3
0 3
1 6
0 8
输出样例
3 2 1 4 5 7 8 6 9 10
算法1
(暴力模拟) $O(n^2)$
根据题目要求,我们只要在每次操作后输出当前的序列即可。 对于每次操作,我们可以暴力模拟,将对应的区间排序即可。 时间复杂度 每次操作需要O(nlogn)的时间复杂度,总共进行m次操作,因此总时间复杂度为O(mnlogn)。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int a[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = i;
}
for (int i = 1; i <= m; i++) {
int p, q;
cin >> p >> q;
if (p == 0) {
sort(a + 1, a + q + 1, greater<int>());
} else {
sort(a + q, a + n + 1);
}
}
for (int i = 1; i <= n; i++) {
cout << a[i] << ' ';
}
cout << endl;
return 0;
}
算法2
(差分) $O(n)$
对于每次操作,我们可以使用差分的思想,只需要记录下每个位置相对于它前一个位置的大小关系即可。 对于降序操作,我们将对应区间内的差分数组全部取相反数,对于升序操作,我们只需要将对应区间的最后一个位置的差分值增加1即可。 最后,我们对差分数组求前缀和,就得到了最终的序列。 时间复杂度 每次操作需要O(n)的时间复杂度,总共进行m次操作,因此总时间复杂度为O(mn)。
C++ 代码
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int diff[n + 1];
for (int i = 1; i <= n; i++) {
diff[i] = 1;
}
for (int i = 1; i <= m; i++) {
int p, q;
cin >> p >> q;
if (p == 0) {
for (int j = 1; j <= q; j++) {
diff[j] *= -1;
}
} else {
diff[q] += 1;
}
}
for (int i = 1; i <= n; i++) {
diff[i] += diff[i - 1];
cout << diff[i] << ' ';
}
cout << endl;
return 0;
}
原文地址: https://www.cveoy.top/t/topic/naoM 著作权归作者所有。请勿转载和采集!