題目
鏈接：PAT (Basic Level) Practice 1045 快速排序
著名的快速排序算法里有一個經(jīng)典的劃分過程：我們通常采用某種方法取一個元素作為主元，通過交換毙芜，把比主元小的元素放到它的左邊业踏，比主元大的元素放到它的右邊戚揭。 給定劃分后的 N 個互不相同的正整數(shù)的排列振峻，請問有多少個元素可能是劃分前選取的主元藻雪？
例如給定, 排列是1饲宿、3特纤、2军俊、4、5捧存。則：
- 1 的左邊沒有元素粪躬，右邊的元素都比它大担败，所以它可能是主元；
- 盡管 3 的左邊元素都比它小镰官，但其右邊的 2 比它小提前，所以它不能是主元；
- 盡管 2 的右邊元素都比它大泳唠，但其左邊的 3 比它大狈网，所以它不能是主元；
- 類似原因笨腥，4 和 5 都可能是主元拓哺。
- 因此，有 3 個元素可能是主元脖母。
輸入格式：
輸入在第 1 行中給出一個正整數(shù) N（≤
?? ）士鸥； 第 2 行是空格分隔的 N 個不同的正整數(shù)，每個數(shù)不超過
谆级。
輸出格式：
在第 1 行中輸出有可能是主元的元素個數(shù)烤礁；在第 2 行中按遞增順序輸出這些元素，其間以 1 個空格分隔肥照，行首尾不得有多余空格脚仔。
輸入樣例：
5
1 3 2 4 5輸出樣例：
3
1 4 5
思路
代碼
#include<stdio.h>
int main()
{
int N;
scanf("%d", &N);
int a[N];
int b[N];
int flag[N];
for(int i = 0; i < N; i++){
scanf("%d", &a[i]);
flag[i] = 0;
}
int max_left = a[0];
int min_right = a[N-1];
int cnt = 0;
for(int i = 0; i < N; i++){
if(max_left < a[i]){
max_left = a[i];
}
if(a[i] >= max_left){
flag[i] = 1;
}
}
for(int i = N - 1; i >= 0; i--){
if(min_right > a[i]){
min_right = a[i];
}
if(a[i] <= min_right && flag[i] == 1){
b[cnt] = a[i];
cnt++;
}
}
printf("%d\n", cnt);
if(cnt == 0){
printf("\n");
}
int f = 0;
for(int i = cnt-1; i >= 0; i--){
if(f == 0){
f = 1;
}
else{
printf(" ");
}
printf("%d", b[i]);
}
return 0;
}
---END---
