HDU 1394 Minimum Inversion Number(樹狀數組)

HDU 1394 Minimum Inversion Number(樹狀數組)

解析：

在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那麼它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。

求逆序對數很自然的想到了樹狀數組，方便又快捷。

對於第一個元素它後面比它小的就一定都會形成逆序對，這樣對於當前的逆序對，在第一個元素移至最後時，它的逆序對數就要減少這個元素的值再減去一，因為此題數值是連續的所以可以直接減，而在移至最後時，大於這個元素的數值的數和它都會形成逆序對。這樣我們在減了之前的值之後還要加上總的元素的個數減去這個元素的值，這樣得到的一個值就是新排列的逆序對數了。例：我們要將a[0]移至末尾，總元素的個數是n，當前的逆序對數是sum，那麼將a[0]移至末尾時，sum += N - a[0] - 1 - a[0] 。

有了這個方法，那麼我們就可以在O(n)的時間內算出所有排列的最小逆序對數了。總的時間復雜度是O(nlogn)。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN=5005;
#define Lowbit(x) ((x)&(-(x)))

int a[MAXN], c[MAXN];
int N;

void ADD(int p, int val){
    while(p>0){
        c[p]+=val;
        p-=Lowbit(p);
    }
}

int getsum(int p){
    int sum = 0;
    p++;
    while(p<=N){
        sum += c[p];
        p+=Lowbit(p);
    }
    return sum;
}

int main(){
    while(~scanf(%d, &N)){
        int i,x;
        int sum = 0;
        memset(c, 0, sizeof(c));
        for(i=0; i