PAT甲级1101 Quick Sort：[C++题解]DP、快速排序划分个数、快排

文章目录

• • 题目分析
  • 题目来源

题目分析

来源:acwing

题意重述：快排的原理，给定一个序列，请判断其中几个数可以作为快速排序划分步骤的分界点。
分界点充分必要条件是：左边的数都比它小，右边的数都比它大（题目给出所有数都不相同，所以是严格的大小关系）。

解题：

想判断第i个数a[i]左边是不是所有的数都小于它，只需要求左边最大的数是不是比a[i]小，如果最大的数都小于a[i]，那么所有的数都小于它。所以我们预处理一个数组$L[N],L[i]$表示$a[1]$ ~ $a[i]$中最大的数

同理，像判断a[i]右边的数是不是都比它大，只需要看右边的最小值是否比它大。所以预处理右边一个数组$R[N],R[i]$表示$a[i]$ ~ $a[n]$中最小的数。

所以我们只需要判断$L[1]$ ~ $L[i-1]$中最大值 小于$a[i]$，$a[i]$小于$R[i]$ ~ $R[n]$中的最小值即可。 记为 $L(i-1)<a[i]<R(i+1)$

AC代码

#include<bits/stdc++.h> using namespace std;const int N = 100010 , INF = 2e9;int n; int a[N],l[N],r[N];int main(){cin >> n;for(int i =1; i<=n; i++) cin>> a[i];//l[i]中存的是前a[1]~a[i]中最大的数，l[3]存的是a[1]到a[3]中最大的数//从前往后枚举for(int i =1; i<= n; i++) l[i] = max(l[i-1], a[i]);//r[i]中存的是从r[i]~r[n]中最小的数//这里从后往前枚举r[n+1] = INF;for(int i = n; i; i--) r[i] = min(r[i+1],a[i]);vector<int> res; //存放结果// 如果a[i]是分界值，放进res里面for(int i =1; i<= n; i++)if(l[i-1] < a[i] && a[i] < r[i+1]) res.push_back(a[i]);cout << res.size()<<endl;if(res.size()){cout << res[0];for(int i=1; i<res.size();i++ ) cout<<" "<<res[i];}else cout<<endl; }

题目来源

PAT甲级1101 Quick Sort
https://www.acwing.com/problem/content/1593/

总结

以上是生活随笔为你收集整理的PAT甲级1101 Quick Sort：[C++题解]DP、快速排序划分个数、快排的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。