PAT A1101 Quicksort

    xiaoxiao2023-09-30  158

    题目大意:

    给出一串不重复的数字,其中主元是满足这样条件的数字:其左边所有数字都小于它,右边所有数字都大于它。让你求出这串数字中的主元个数并列出。

    注意点:

    确定一个数字是否是主元的方法:对当前序列进行sort排序,如果当前数字次序不变,且大于其左边所有数字中的最大值,则是主元。根据格式要求,如果主元个数为0,则需要第二行为空行。

    代码:

    //5 //1 3 2 4 5 #include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int maxn = 100010; int n,a[maxn] = {0},b[maxn]={0},v[maxn]={0}; int main() { cin>>n; for(int i=0;i<n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } sort(a,a+n); int ans = 0,max = 0; for(int i=0;i<n;i++) { //cout<<"*"<<" "<<a[i]; if(a[i]==b[i]&&b[i]>max) v[ans++]=a[i]; if(b[i]>max) max=b[i]; } cout<<ans<<endl; for(int i=0;i<ans;i++) { if(i!=0) printf(" "); printf("%d",v[i]); } if(ans==0) printf("\n"); return 0; }
    最新回复(0)