hdu 1394 Minimum Inversion Number（暴力/線段樹/樹狀數組）

題目：http://acm.hdu.edu.cn/showproblem.php?pid=1394

題意：一個數列可以把任意隊首元素挪到對尾，求這些可能中最小的逆序對數，數列由0，到n-1組成。

暴力：可以通過這個資料看出這個結論。

如果求出第一種情況的逆序列，其他的可以通過遞推來搞出來，一開始是t[1],t[2],t[3]....t[N]

它的逆序列個數是N個，如果把t[1]放到t[N]後面，逆序列個數會減少t[1]個，相應會增加N-(t[1]+1)個 

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,a[5005],cnt;
    while(scanf("%d",&n)!=EOF){
        int ans=999999999;
        cnt=0;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
                if(a[i]>a[j])
                    cnt++;
        if(ans>cnt)
            ans=cnt;
        for(int i=0;i<n;i++){
            cnt=cnt-a[i]+n-1-a[i];
            if(ans>cnt)
                ans=cnt;
        }
        printf("%d\n",ans);
    }
    return 0;
}
           

神奇的線段樹：

仍然是剛才結論，與剛才類似，隻是線段樹将n^2優化了下。

1.按順序建一棵空樹，以後葉子結點的sum都放一

2.每次for查有幾個比他大的，即a【i】到n-1有幾個數，

3.update要在後面，因為查的時候不能包擴a[i]

/*都從 1 開始建樹，保持習慣*/
#include<cstdio>
#define N 50050
int num[N];
struct Tree{
    int l;
    int r;
    int sum;
}tree[4*N];


void build(int t,int l,int r){
    tree[t].l=l;
    tree[t].r=r;
    tree[t].sum=0;
    if(tree[t].l==tree[t].r){
        tree[t].sum=0;
        return;
    }
    int mid=(l+r)/2;
    build(2*t,l,mid);
    build(2*t+1,mid+1,r);
    //tree[t].sum=tree[2*t].sum+tree[2*t+1].sum;
}
void update(int t,int pos,int val){
    if(tree[t].l==tree[t].r){
        tree[t].sum++;
        return;
    }
    int mid=(tree[t].l+tree[t].r)/2;
    if(pos<=mid)
        update(2*t,pos,val);
    else
        update(2*t+1,pos,val);
    tree[t].sum=tree[2*t].sum+tree[2*t+1].sum;
}
int query(int t,int l,int r){
    if(l<=tree[t].l&&r>=tree[t].r)
        return tree[t].sum;
    int mid=(tree[t].l+tree[t].r)/2,ans=0;
    if(l<=mid) ans+=query(2*t,l,r);
    if(r>mid)  ans+=query(2*t+1,l,r);
    return ans;
}


int main(){
    int n,a[5005],sum;
    while(scanf("%d",&n)!=EOF){
        sum=0;
        int ans=999999999;
        build(1,1,n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){
            sum+=query(1,a[i]+1,n);
            update(1,a[i],1);
        }
        if(ans>sum)
            ans=sum;
        //printf("%d\n",sum);
        for(int i=1;i<=n;i++){
            sum=sum-a[i]+n-1-a[i];
            if(ans>sum)
                ans=sum;
        }
        printf("%d\n",ans);
    }
    return 0;
}
           

求逆序對最快的是樹狀數組

#include<bits/stdc++.h>
using namespace std;

int n,tree[100005],a[5005];

int lowbit(int i){
    return i&(-i);
}
void update(int i,int x){
    while(i<=n){
        tree[i]+=x;
        i+=lowbit(i);
    }
}
int query(int i){
    int sum=0;
    while(i>0){
        sum+=tree[i];
        i-=lowbit(i);
    }
    return sum;
}
int main(){
    while(scanf("%d",&n)!=EOF){
        memset(tree,0,sizeof(tree));
        int sum=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            update(a[i]+1,1);
            sum+=i-query(a[i]+1);
        }
        int ans=sum;
        for(int i=1;i<=n;i++){
            sum=sum-a[i]+n-1-a[i];
            if(ans>sum)
                ans=sum;
        }
        printf("%d\n",ans);
    }
    return 0;
}