题目大意
该算法通过交换两个相邻的序列元素来处理 n 个不同整数的序列，直到序列按升序排序，求至少交换几次。
思路
有一个结论：只要有一对逆序对那么一定会发生一次交换（参考冒泡排序过程）。
那么就只需要求出该序列的逆序对数即可。
方法一
使用归并排序求出逆序对
#include<iostream>
using namespace std;
const int N = 500010;
int a[N],tmp[N];
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 i = l, j = mid+1, cnt = 0;
while(i <= mid && j <= r){
if(a[i] > a[j]) tmp[cnt++] = a[j++], ans += mid-i+1;//说明i到mid都可以和j组成逆序对
else tmp[cnt++] = a[i++];
}
while(i <= mid) tmp[cnt++] = a[i++];
while(j <= r) tmp[cnt++] = a[j++];
for(int i = 0; i < cnt; i++) a[l+i] = tmp[i];
}
int main(){
cin.tie(0)->sync_with_stdio(false);
int n;
while(cin>>n && n){
for(int i = 0; i < n; i++) cin>>a[i];
ans = 0;
merge_sort(0,n-1);
cout<<ans<<'\n';
}
return 0;
}
方法二
树状数组求出逆序对，由于 a i a_i ai?的范围为[0,999999999]，所以需要对数组进行离散化
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 500010;
int a[N],b[N],last;
long long ans,tr[N];
void b_unique(int st,int ed){
int j = st;
for(int i = st; i < ed; i++)
if(b[i] != b[j]) b[++j] = b[i];
last = j;
}
int find(int x){
int l = 1, r = last;
while(l < r){
int mid = l+r>>1;
if(b[mid] < x) l = mid+1;
else r = mid;
}
return l;
}
int lowbit(int x){
return x&-x;
}
long long sum(int x){//返回tr[1]+...+tr[x]的和
long long res = 0;
for(int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
void add(int x){//避免x==0
for(int i = x; i <= last; i += lowbit(i)) tr[i]++;
}
int main(){
cin.tie(0)->sync_with_stdio(false);
int n;
while(cin>>n && n){
ans = 0;
memset(tr,0,sizeof tr);
for(int i = 1; i <= n; i++) {
cin>>a[i]; b[i] = a[i];
}
sort(b+1,b+n+1); b_unique(1,n+1);
for(int i = 1; i <= n; i++){
int x = find(a[i]);
ans += sum(last) - sum(x);//获得tr[x+1]到tr[last]的和
add(x);//tr[x]到tr[last]都加1
}
cout<<ans<<'\n';
}
return 0;
}
