给出一个序列 相邻的两个数可以进行交换 问最少交换多少次可以让他变成递增序列 每个数都是独一无二的
其实就是问冒泡往后 最多多少次
但是按普通冒泡记录次数一定会超时
冒泡记录次数的本质是每个数的逆序数相加 因为只有后面的数比自己笑才能交换
但是暴力求逆序数也会超时
于是用树状数组求 从最后往前看 每次求sum相加
但是数据的范围根本开不出来树状数组...
但是由于n最多只有五十万 所以把它离散化一下 把这n个数变成1~n
技巧就是先按大小排序 然后把他们变成1~n 然后按照结构体中的顺序再排回来
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<math.h>
using namespace std;
struct node
{
int zhi;
int whe;
};
int n;
int cmp(node a,node b)
{
return a.zhi<b.zhi;
}
int c[500050];
node a[500050];
int lowbit(int x)
{
return x&(-x);
}
long long sum(int x)
{
long long sum=0;
for(int i=x;i>=1;i-=lowbit(i))
{
sum+=c[i];
}
return sum;
} void add(int x)
{
for(int i=x;i<=n;i+=lowbit(i))
{
c[i]+=1;
}
}
int cmpp(node a,node b)
{
return a.whe<b.whe;
}
int main(){
while(~scanf("%d",&n))
{
if(n==0)
break;
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].zhi);
a[i].whe=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
a[i].zhi=i;
}
sort(a+1,a+1+n,cmpp);
long long ans=0;
for(int i=n;i>=1;i--)
{
long long summ=sum(a[i].zhi);
add(a[i].zhi);
ans+=summ;
}
printf("%I64d\n",ans);
}
}