2016年8月29日 星期一

TOJ 11 bubble

TOJ 11 bubble

題目概述:腦書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' ;
}