1045. 快速排序(25)

2019-11-11 07:10:27

字體：大中小

來源：轉載

供稿：網友

著名的快速排序算法里有一個經典的劃分過程：我們通常采用某種方法取一個元素作為主元，通過交換，把比主元小的元素放到它的左邊，比主元大的元素放到它的右邊。給定劃分后的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個空格分隔，行末不得有多余空格。

輸入樣例： 5 1 3 2 4 5 輸出樣例： 3 1 4 5

#include <iostream>#include <algorithm> using namespace std;int main(){ int N; cin>>N; int num[N]; int sorted[N]; for ( int i = 0 ; i < N ; i++){ cin>>num[i]; sorted[i] = num[i]; } sort(sorted,sorted+N); int len = 0; int pivot[N]; int max = 0; for ( int i = 0 ; i < N ; i++){ if ( max < num[i]){ max = num[i]; } if ( num[i] == sorted[i] && max == num[i]){ pivot[len] = num[i]; len++; } } cout<<len<<endl; cout<<pivot[0]; for ( int i = 1 ; i < len ; i++){ cout<<" "<<pivot[i]; } return 0;}

（PS:bug找不出來了） 這里寫圖片描述