[C++] PAT 1101 Quick Sort (25分)

Sample Input:

5
1 3 2 4 5

Sample Output:

3
1 4 5

题解：

直接先对数组排序，
如果排序后的元素i下标index在这里插入代码片保持不变，并且i大于原数组中i之前最大的元素max，则将i加入结果数组

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;struct node{int index;long long value;
};
int n;
vector<node> index;
bool cmp(node &a,node &b){return a.value < b.value;
}int main(){cin >> n;index.resize(n);for(int i=0;i<n;i++){scanf_s("%d",&index[i].value);index[i].index = i;}vector<node> temp_index = index;sort(index.begin(),index.end(),cmp);vector<int> ans;int max = -1;for(int i=0;i<n;i++){if(index[i].value == i && index[i].value > max){ans.push_back(index[i].value);}if(temp_index[i].value > max){max = index[i].value;}}cout << ans.size() << endl;for(int i=0;i<ans.size();i++){cout << ans[i];if(i!=ans.size()-1){cout << " ";}}cout << endl;system("pause");return 0;
}