1101. Quick Sort.md

pat 甲级 1101. Quick Sort、乙级 1045. 快速排序

题意概述

著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的 N 个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？

输入输出格式

输入在第 1 行中给出一个正整数 N，第 2 行是空格分隔的 N 个不同的正整数。

在第 1 行中输出有可能是主元的元素个数；在第 2 行中按递增顺序输出这些元素，其间以 1 个空格分隔，行首尾不得有多余空格。

数据规模

$$N<=10^5$$

算法设计

题目要求统计出在一个序列 A 中比左侧数都大，比右侧数都小所有的数。可以定义两个辅助数组leftMax和rightMin，表示存储相应位置处左侧位置的最小值，右侧位置的最大值。同时遍历这三个数组，如果序列 A 在位置 i 处的元素A[i]>leftMax[i] and A[i]<rightMin[i]，那么A[i]即为主元。遍历一次就可以找到所有主元。

注意点

如果主元个数为 0，第二行需要输出一个空行。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni;
    cin >> ni;
    vector<gg> v(ni), leftMax(ni, INT_MIN), rightMin(ni, INT_MAX);
    for (gg& i : v) {
        cin >> i;
    }
    for (gg i = 1; i < ni; ++i) {
        leftMax[i] = max(leftMax[i - 1], v[i - 1]);
    }
    for (gg j = ni - 2; j >= 0; --j) {
        rightMin[j] = min(rightMin[j + 1], v[j + 1]);
    }
    vector<gg> ans;
    for (gg i = 0; i < ni; ++i) {
        if (v[i] > leftMax[i] and v[i] < rightMin[i]) {
            ans.push_back(v[i]);
        }
    }
    cout << ans.size() << "\n";
    for (gg i = 0; i < ans.size(); ++i) {
        cout << (i == 0 ? "" : " ") << ans[i];
    }
    cout << "\n";
    return 0;
}