1045 快速排序 (25 分)
著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的 N 个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？
例如给定 N=5, 排列是1、3、2、4、5。则：
1 的左边没有元素，右边的元素都比它大，所以它可能是主元；
尽管 3 的左边元素都比它小，但其右边的 2 比它小，所以它不能是主元；
尽管 2 的右边元素都比它大，但其左边的 3 比它大，所以它不能是主元；
类似原因，4 和 5 都可能是主元。
因此，有 3 个元素可能是主元。
输入格式：
输入在第 1 行中给出一个正整数 N（≤10^5）； 第 2 行是空格分隔的 N 个不同的正整数，每个数不超过 10^9 。
输出格式：
在第 1 行中输出有可能是主元的元素个数；在第 2 行中按递增顺序输出这些元素，其间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
5
1 3 2 4 5
输出样例：
3
1 4 5
分析：
一般这种25分的题直接用多层循环是一定超时的
思路：
原数组和sort排序之后的数组进行比较
如果arr[i]和ord[j]的i、j不等则说明arr[i]不是主元的
如：
arr 1 3 2 4 5
ord 1 2 3 4 5
结果：1 4 5
但还有一种情况，如果有多个重复的数字
如：
arr 1 4 2 3 3 5
ord 1 2 3 3 4 5
此时的看似结果是1 3 5 其实是 1 5
需要对arr[i]进行判断，其是否在其左边是最大值，在其右边是最小值 ，即为主元
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int arr[100011];//原数组
int ord[100011];//sort排序后的数组
int xxx[100011];//
int main(){
int N;
cin>>N;
for(int i=0;i<N;i++){
cin>>arr[i];
}
memcpy(ord, arr, N * sizeof(int));//复制数组 头文件<cstring>或<string.h>
sort(ord,ord+N); //<algorithm>
int j=0;
int count=0;//计算主元个数
int max=0;
//int min=ord[N-1];
//arr 1 4 2 3 3 5
//ord 1 2 3 3 4 5
//结果：
//2
//1 5
for(int i=0;i<N;i++){//如果arr[i]和ord[j]的i、j不等则不匹配，则j++、i++，继续下一轮的检查匹配
if(arr[i]>max){//找arr[i]左边的最大值
max=arr[i];
}
if(ord[j]==arr[i]){//如果arr和ord对应，且左边是最大值，在右边是最小值，则说明是主元
if(max==arr[i]) {//测试点3答案错误 ，这里只加了个左边最大值判断水过了，
xxx[count]=arr[i];
count++;
}
}
j++;
}
cout<<count<<endl;
for(int i=0;i<count;i++){
if(i!=0)cout<<" ";
cout<<xxx[i];
}
cout<<endl; //没有加这个回车测试点2会格式错误
return 0;
}