本文主要是介绍sicily 4425Easy Sort，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
进行一次翻转之后，接下的翻转肯定只交换相邻的数，统计逆序对。
用树状数组做，新序列保存在arr中，
没读入一个arr[i],就在c[arr[i]]位置加1，这时候arr[i]与之前输入的i个数中构成逆序的就是i-sum(arr[i])拉。。
#include<iostream>
#include<cstdio>#include<cstring>
#include<algorithm>
using namespace std;
int arr[110000];
int ans = 0;
int c[110000];
int n;
int lowbit(int x)//计算lowbit
{
return x&(-x);
}
void add(int i,int val)//将第i个元素更改为val
{
while(i<=n)
{
c[i]+=val;
i+=lowbit(i);
}
}
int sum(int i)//求前i项和
{
int s=0;
while(i>0)
{
s+=c[i];
i-=lowbit(i);
}
return s;
}
int main()
{
int t;
scanf("%d",&t);
long long ans = 0;
while(t--){
ans = 0;
/// int n;
scanf("%d",&n);
for(int i = 0;i<n;i++)scanf("%d",&arr[i]);
int low = 0,high = 1;
while(1){
if(high>=n)break;
while(high<n && arr[high]<arr[high-1])high++;
if(high-low==1){
low++;
high = low+1;
continue;
}
for(int i = 0;i<(high-low)/2;i++){
int tmp = arr[i+low];
arr[i+low] = arr[high-1-i];
arr[high-1-i] = tmp;
}
low = high;
high = low+1;
ans++;
}
memset(c,0,sizeof(c));
for(int i = 1;i<=n;i++){
add(arr[i-1],1);
ans+=i-sum(arr[i-1]);
}
printf("%lld\n",ans);
}
return 0;
}
这篇关于sicily 4425Easy Sort的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
