TOJ 11 bubble

TOJ 11 bubble

http://toj.tfcis.org/oj/pro/11/

題目概述:腦書p.368

求一個數列作泡沫排序需要幾次交換。

思路:

因為想寫寫看merge_sort就來寫這個了XD

以下給出merge_sort的作法與BIT的做法。

merge_sort作法

//By SCJ

#include<iostream>

using namespace std;

#define endl '\n'

#define maxn 2000000

int a[maxn+2],tp[maxn+2];

long long ans;

void merge_sort(int l,int r)

{

if(l==r) return ;

int mid=(l+r)>>1;

merge_sort(l,mid);

merge_sort(mid+1,r);

int ln=l,rn=mid+1,nw=l;

while(ln<=mid&&rn<=r)

{

if(a[ln]>a[rn]) tp[nw++]=a[rn++],ans+=mid-ln+1;

else tp[nw++]=a[ln++];

}

while(rn<=r) tp[nw++]=a[rn++];

while(ln<=mid) tp[nw++]=a[ln++];

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

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

int n;cin>>n;

for(int i=1;i<=n;++i) cin>>a[i];

merge_sort(1,n);

cout<<ans<<endl;

}

BIT 作法

//By SCJ

#include<iostream>

using namespace std;

int n,tmp,bit[2000005];

long long ans;

int add(int i,int x)

{

   while(i<=n)

   {

       bit[i]+=x;

       i+=i&-i;

   }

}

int sum(int i)

{

   int s=0;

   while(i>0)

   {

       s+=bit[i];

       i-=i&-i;

   }

   return s;

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   cin>>n;

   for(int i=0;i<n;++i)

   {

       cin>>tmp;

       ans+=i-sum(tmp);

       add(tmp,1);

   }

   cout << ans << '\n' ;

}