排序刷题12 -双向排序
题目来源：[蓝桥杯 2021 省 B] 双向排序 - 洛谷
最近开始刷蓝桥杯的题目了，本小白表示有些题目好难阿，研究生组哭晕(((φ(◎ロ◎;)φ)))。这道题自己做只能达到60分，本小白表示100分优化不会惹，先拿点分后面再看别人的思路吧。
解题思路：想到了用sort()函数解决，发现也就60分，超时了。不过没关系能拿一点是一点。（hahahaha~，心态有点好）
解题步骤：
- 初始化一个大小为 n+1 的数组（考虑到序列是从1开始的），用于记录每个位置的元素值。
- 遍历操作指令，根据操作类型更新序列：
- 当 p_i = 0 时，表示需要将前 q_i 个元素降序排列。这里可以标记一个断点 q_i，表示 1到 q_i 需要降序排列。
- 当 p_i = 1 时，表示需要将从 q_i 到 n$的元素升序排列。同样，标记一个断点 q_i，表示 q_i到 n 需要升序排列。
- 最后，根据这些断点信息，构造最终的序列。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;int main()
{// 读入序列长度 n 和操作次数 mint n, m;cin >> n >> m;// 初始化序列 arr，按照题目要求填充从 1 到 n 的整数vector<int> arr(n);for (int i = 0; i < n; i++){arr[i] = i + 1;}// 对每一个操作进行处理for (int i = 0; i < m; i++){int p, q;cin >> p >> q; // 读入操作类型 p 和操作参数 q// 根据操作类型对序列的相应部分进行排序if (p == 0)// p 为 0 时，对前 q 个元素执行降序排序sort(arr.begin(), arr.begin() + q, greater<int>());else// p 为 1 时，对从第 q 个元素到末尾的部分执行升序排序sort(arr.begin() + q - 1, arr.end());}// 输出最终的序列for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;return 0;
}