hdu 1394

題意：給出一個數組是0 ~n-1的排列，然後将第一個數一個一個地加入到數組的最後，使得形成的數組的逆序對最少，輸出最少的逆序對；

思路：因為是0~n-1的排列，防止樹狀數組在0處無法自增，a[i] ++ ，形成1~n的排列。是以第一個數的形成的逆序對的數量是比它小的數的個數即a[1] - 1;比他的的數目為n - a[1]，即為到了最後一位所形成的逆序對。是以每把一個數加入到最後，産生的改變是n - a[i] - (a[i] - 1);

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 10000 + 2;
#define INF 0x3f3f3f3f
#define clr(x,y) memset(x,y,sizeof x )
typedef long long ll;

#define eps 10e-10
const ll Mod = 1000000007;

int n;
int a[maxn];
int tree[maxn];
inline int lowbit(int x)
{
    return x & (-x);
}
void update(int x,int val)
{

    for(int i = x; i < maxn; i += lowbit(i))
    {
        tree[i] += val;
    }
}
int get_sum(int x)
{
    int ret = 0;
    for(int i = x; i > 0; i -= lowbit(i))
        ret += tree[i];
    return ret;
}
int main()
{
    while( ~ scanf("%d",&n))
    {
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d",&a[i]);
            a[i] ++;
        }
        clr(tree,0);
        int sum = 0;
        for(int i = n; i >= 1; i --)
        {
            sum += get_sum(a[i]);
            update(a[i],1);
        }
        int ans = sum;
        int t = sum;
        for(int i = 1; i <= n; i ++)
        {
            t += n - a[i] - (a[i] - 1);
            ans = min(ans,t);
        }
        cout << ans << endl;
    }
    return 0;
}