PAT 乙级 1045

题目

题目地址：PAT 乙级 1045

题解

本题的解法比较巧妙，刚开始的试着用暴力求解，果不其然时间超限……

变换思路，既然对于每个元素来说满足的条件是前小后大，那么对数组排序，对应的位置相等的即为题设要求的“可能主元”，但是还有一个条件要保证当前是从左向右遍历的最大值；总结一下两个条件：1. 排序后对应位置数字相等；2. 当前操作元素是从左向右遍历中的最大值

同时还要注意，当输入n值为0时，除了需要输出“可能主元”的个数之外，还需要保留换行符‘\n’

代码

 #include <iostream>

 #include <algorithm>

 #include <vector>

 using namespace std;

 int main() {

     vector<int> num;

     vector<int> sortnum;

     vector<int> result;

     int n = ;

     cin >> n;

     while (n--) {

         int tmp = ;

         cin >> tmp;

         num.push_back(tmp);

         sortnum.push_back(tmp);

     }

     sort(sortnum.begin(), sortnum.end());

     int maxx = ;

     for (int i = ; i < num.size(); i++) {

         if (num[i] > maxx)

             maxx = num[i];

         if (num[i] == sortnum[i] && num[i] >= maxx)

             result.push_back(sortnum[i]);

     }

     cout << result.size() << endl;

     for (int i = ; i < result.size(); i++) {

         if (i != result.size() - )

             cout << result[i] << ' ';

         else

             cout << result[i];

     }

     cout << endl;

     return ;

 }