NO IMAGE

解題思路:這道題是求迴圈陣列中逆序數最小值,求逆序數這裡肯定是用樹狀陣列。只是這裡有一點點變化,由於題目中n位數是0-n-1的一個排列,所以num[i]可表示為比num[i]小的數的個數。把第一位的數挪到最後一位,那麼整個序列的逆序數變化為ans =ans –  num[0] (n-1-num[0]),num[0]表示後面的n-1位對逆序數的貢獻,n-1-num[0]表示把最後一位挪過來對逆序數所作出的貢獻。由於最小是為0,所以更新樹狀陣列時多加個1。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 5005;
int num[maxn];
int n,tree[maxn<<2];
int lowbit(int x)
{
return x & -x;
}
void update(int x,int d)
{
for(int i = x; i <= n; i  = lowbit(i))
{
tree[i]  = d;
}
}
int getsum(int x)
{
int sum = 0;
for(int i = x; i > 0; i -= lowbit(i))
{
sum  = tree[i];
}
return sum;
}
int main()
{
while(cin >> n)
{
memset(tree,0,sizeof(tree));
for(int i = 1; i <= n; i  )
{
scanf("%d",&num[i]);
}
int ans = 0;
for(int i = 1; i <= n; i  )
{
update(num[i] 1,1);
ans  = i - 1 - getsum(num[i]);
}
int MIN = ans;
for(int i = 1; i <= n; i  )
{
ans = ans - num[i]   (n - 1 - num[i]);
MIN = min(MIN,ans);
}
cout << MIN << endl;
}
return 0;
}