PAT乙級1045

1045. 快速排序(25)

時間限制

200 ms

記憶體限制

65536 kB

代碼長度限制

8000 B

判題程式

Standard

作者

CAO, Peng

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

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<int> v;
  int temp;
  while (N--)
  {
    cin >> temp;
    v.push_back(temp);
  }
  vector<int> min, max;//儲存每個數在它之前的這一段中的最大數和在它之後的這一段中的最小數
  int Min = 1000000001, Max = 0;
  for (int i = 0; i < v.size(); i++)
  {
    if (Min > v[v.size()-1-i])
    {
      Min = v[v.size()-1-i];
      
    }
    min.push_back(Min);
    if (Max <v[i])
    {
      Max = v[i];
      
    }
    max.push_back(Max);
  }
  reverse(min.begin(), min.end());//因為我用的vector，需要逆轉下，才能與數字相對應
  vector<int> vv;
  for (int i = 0; i < v.size(); i++)
  {
    if (min[i] == max[i])
    {
      vv.push_back(v[i]);
    }
  }

  cout << vv.size() << endl;
  sort(vv.begin(), vv.end());
  if (!vv.size())
    cout << endl;//這個地方是個坑，當0個元素能夠成為主元時，還得輸出空行，題目沒說清
  else
  for (int i = 0; i < vv.size(); i++)
  {
    cout << vv[i];
    if (i != vv.size() - 1)
      cout << " ";
    else
      cout << endl;
  }
  
  return 0;
}