著名的快速排序算法里有一個(gè)經(jīng)典的劃分過(guò)程：我們通常采用某種方法取一個(gè)元素作為主元宝剖，通過(guò)交換憔鬼，把比主元小的元素放到它的左邊躁倒，比主元大的元素放到它的右邊。 給定劃分后的N個(gè)互不相同的正整數(shù)的排列粪般，請(qǐng)問(wèn)有多少個(gè)元素可能是劃分前選取的主元？
例如給定N = 5, 排列是1污桦、3亩歹、2、4凡橱、5小作。則：
1的左邊沒(méi)有元素，右邊的元素都比它大梭纹，所以它可能是主元躲惰；
盡管3的左邊元素都比它小，但是它右邊的2它小变抽，所以它不能是主元础拨；
盡管2的右邊元素都比它大，但其左邊的3比它大绍载，所以它不能是主元诡宗；
類(lèi)似原因，4和5都可能是主元击儡。
因此塔沃，有3個(gè)元素可能是主元。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a[100001], b[100001],c[100001];
int n,cnt = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(a, a + n);
int max=-1;
for (int i = 0; i < n; i++) {
if(a[i] == b[i]&&b[i]>max)
c[cnt++] = b[i];
if(b[i]>max)
max=b[i];
}
printf("%d\n", cnt);
for(int i = 0; i < cnt; i++) {
if (i != 0) printf(" ");
printf("%d", c[i]);
}
printf("\n");
}
主元的位置一定是數(shù)組排序好之后的位置阳谍，至于它之前之后的元素蛀柴，只需要知道它前面的一定小于它螃概，后面的一定大于它。確定好位置以及它大于前面的任意元素鸽疾，它就一定大于后面的任意元素吊洼，因?yàn)槭琼樞虮闅v，所以只要確定每次后移之后前面元素的最大值
