PAT 乙级 1045. 快速排序(25)-白红宇

PAT 乙级 1045. 快速排序(25)

阅读量：6836 次

发布时间：2019-06-26

本文共 1018 字，大约阅读时间需要 3 分钟。

树状数组+离散化。把所有数字离散化到1--n，设离散化之后的数组为m[a[i]]，对于主元，只有m[a[i]]==i的m[a[i]]才可能。然后要算m[a[i]]之前比m[a[i]]小的个数是否为m[a[i]]-1，如果是的，那么就是主元，利用树状数组可以在log(n)效率内运算前缀和或者更新单点。坑点就是如果答案是0，那么要输出0和一个空行。

#include
     
      #include
      
       #include
       
        #include
        #include
         
          using namespace std;const int maxn=100000+10;int a[maxn],ans[maxn],c[maxn],b[maxn];int n;map
          
           m;int lowbit(int x){ return x&(-x);}void update(int a,int b){ for(int i=a;i<=n;i=i+lowbit(i)) c[i]+=b;}int get(int a){ int res=0; for(int i=a;i>0;i=i-lowbit(i)) res+=c[i]; return res;}void lsh(){ sort(b+1,b+1+n); for(int i=1;i<=n;i++) m[b[i]]=i;}int main(){ scanf("%d",&n); int k=0; memset(c,0,sizeof c); m.clear(); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } lsh(); for(int i=1;i<=n;i++) { if(m[a[i]]==i) { int num=get(m[a[i]]-1); if(num==m[a[i]]-1) ans[k++]=m[a[i]]; } update(m[a[i]],1); } sort(ans,ans+k); printf("%d\n",k); for(int i=0;i

转载于:https://www.cnblogs.com/zufezzt/p/5129098.html

你可能感兴趣的文章