著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的N个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？ 例如给定N = 5, 排列是1、3、2、4、5。则： - 1的左边没有元素，右边的元素都比它大，所以它可能是主元； - 尽管3的左边元素都比它小，但是它右边的2它小，所以它不能是主元； - 尽管2的右边元素都比它大，但其左边的3比它大，所以它不能是主元； 类似原因，4和5都可能是主元。 因此，有3个元素可能是主元。
输入格式： 输入在第1行中给出一个正整数N（<= 105）； 第2行是空格分隔的N个不同的正整数，每个数不超过109。
输出格式： 在第1行中输出有可能是主元的元素个数；在第2行中按递增顺序输出这些元素，其间以1个空格分隔，行末不得有多余空格。
程序：
#include <stdio.h> #include <stdlib.h> #include <algorithm> // #include <iostream> using namespace std; int main() { int N, x; scanf("%d\n", &N); int MaxArr[100000]; // 记录从左到右每一个MAX的下标 long Arr[100000]; // 记录输入的数据 int MAXNUM = 0; // 记录当前的最大值 int j = 0; // MaxArr的下标 for (int i = 0; i < N; i++) { scanf("%d", &x); Arr[i] = x; if (x > MAXNUM) { MAXNUM = x; MaxArr[j++] = i; // 记录下标 } } int idx = j - 1; // 倒着寻找.因为左边一定是符合的，但右边不一定 // cout << "idx " << idx << endl; long outArr[100000]; int outIdx = 0; // 记录输出结果的下标 int upBound = N - 1; // 记录循环的上界 for (; idx >= 0; idx--) { int flag = 0; long data = Arr[MaxArr[idx]]; for (int k = MaxArr[idx] + 1; k <= upBound; k++) { // cout << Arr[k] << " " << data << endl; if (Arr[k] <= data) { flag = 1; break; } } if (!flag) { outArr[outIdx++] = data; upBound = MaxArr[idx]; } } sort(outArr, outArr+outIdx); // 打印结果------------这个还需要在为0个结果时再输出一个换行符... printf("%d\n", outIdx); if (outIdx == 0) { printf("\n"); return 0; } printf("%ld", outArr[0]); for (int n = 1; n < outIdx; n++) { printf(" %ld", outArr[n]); } printf("\n"); return 0; }