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' ;
}
