ACM_小明滚出去？（求逆序数）

Problem Description:

老师：“小明，写一个排序算法”；

小明：

void mysort(int a[],int n) //n为数组a的元素个数

{

    int i,j;

    for(j=0;j< n-1;j++)

        for(i=0;i< n-1;i++)

        {

            if(a[i] >a[i+1])//数组元素大小按升序排列

            {

            	swap(a[i],a[i+1]);//交换

            }

        }

}

老师:“好，那么，问题来了，给定一个数组，按你这个算法排序，需要的交换次数是多少？回答对了今天就可以不用滚出去。”

小明按他的这个算法试了一下，发现超时了，不想天天被老师叫滚出去，小明只好求助于你，你能帮助小明今天不用滚出去么？

Input:

输入包含多组数据(EOF)，每组数据第一行是一个整数n(1<=n<=10^5)，第二行有n个整数(<=10^5);

Output:

对于每组数据，输出小明排序算法的交换次数。

Sample Input:

Sample Output:

1

10

0
解题思路：求冒泡排序的交换次数其实就是求这个序列的逆序数，归并排序水过！
AC代码一之归并排序：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=1e5+;

 typedef long long LL;

 int n,a[maxn],tmp[maxn];LL ans;

 void _merge(int l,int m,int r){

     int i=l,j=m+,k=l;

     while(i<=m&&j<=r){

         if(a[i]>a[j]){tmp[k++]=a[j++];ans+=(LL)m-i+;}

         else tmp[k++]=a[i++];

     }

     while(i<=m)tmp[k++]=a[i++];

     while(j<=r)tmp[k++]=a[j++];

     for(int i=l;i<=r;++i)a[i]=tmp[i];

 }

 void _merge_sort(int l,int r){

     if(l<r){

         int m=(l+r)>>;

         _merge_sort(l,m);

         _merge_sort(m+,r);

         _merge(l,m,r);

     }

 }

 int main(){

     while(~scanf("%d",&n)){

         for(int i=;i<n;++i)scanf("%d",&a[i]);

         ans=;_merge_sort(,n-);

         printf("%lld\n",ans);

     }

     return ;

 }

AC代码二之树状数组：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 typedef long long LL;

 int n,val,aa[maxn],tar[maxn];

 struct node{int val,id;}nod[maxn];

 bool cmp(node a,node b){return a.val<b.val;}

 int lowbit(int x){return x & -x;}

 void update(int x,int val){

     while(x<=n){aa[x]+=val;x+=lowbit(x);}

 }

 int getsum(int x){

     int ret=;

     while(x>){ret+=aa[x];x-=lowbit(x);}

     return ret;

 }

 int main(){

     while(cin>>n){

         LL ans=;

         memset(aa,,sizeof(aa));

         for(int i=;i<=n;++i){cin>>nod[i].val;nod[i].id=i;}

         sort(nod+,nod+n+,cmp);

         for(int i=;i<=n;++i)tar[nod[i].id]=i;

         for(int i=;i<=n;++i){update(tar[i],);ans+=i-getsum(tar[i]);}

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

ACM_小明滚出去？（求逆序数）

Problem Description:

Input:

Output:

Sample Input:

Sample Output:

最新文章

热门文章