题目链接：1045 快速排序 (25分)
题目
解题思路
这个题有点动态规划的意思。
主元的意思就是，这个数的左边全是小于它的数，右边全是大于它的数。这样在快排的时候它就有可能作为主元，就是不动的那个。
- 将数按顺序存起来
- 从前往后遍历，将前面的最大的数存起来与当前数比较，如果这个数前面的最大值小于当前值，说明这个数前面都是小于它的数
- 从后往前遍历，将后面的最小的数存起来与当前数比较，如果这个数后面的最小值大于当前值，说明这个数后面都是大于它的数
- 获得两组标记之后，求交集，交集中的数即为
前面的数都小，后面的数都大的主元数了
代码
#include <iostream>
using namespace std;
#include <set>
#include <vector>
const int infn = int(1e9 + 9);int main() {ios::sync_with_stdio(0); cin.tie(0);int t; cin >> t;vector<int> v;for(int i = 0; i < t; i++) {int a; cin >> a; v.push_back(a);}int m = 0;set<int> sa;for(int i = 0; i < t; i++) if (m < v[i]) m = v[i], sa.insert(v[i]);m = infn;set<int> sb;for(int i = t - 1; i >= 0; i--) if (m > v[i]) m = v[i], sb.insert(v[i]);v.clear();int c = 0;for (int a : sa) if (sb.find(a) != sb.end()) v.push_back(a), c += 1;cout << c << endl;bool f = false;for (int a : v) {if (f) cout << ' '; cout << a; f = true;}cout << endl;return 0;
}
请多多支持猹的个人博客 H_On 个人小站
因为猹的小站真的还挺可的，所以那边更新的也比较勤奋，感谢关注~我会努力的(? ?_?)?