HDU 1394 Minimum Inversion Number(單點更新) -开发者知识库

HDU 1394 Minimum Inversion Number(單點更新) -开发者知识库,第1张

題目鏈接

題目分析
1、題目要求輸入一個整數n(n<=5000),隨后輸入n個數,這n個數是0~n-1的全排列
2、對於這組序列,可以做一些變換,把前面的m(m>=0)個數放到序列的最后
3、對於所有的變換后的序列,求個數最少的逆序對是多少
實現方法
1、線段樹
2、首先建立一顆空樹,樹根為1,所有的結點的值都是0

3、每輸入一個數,對線段樹進行單點更新,更新之后逆序對數也要改變

  • 如果輸入的數a[i]不等於n-1,那就只需查看從a[i] 1~n-1之間已經輸入過的數有多少個
  • 這么理解:如果a[i] 1~n-1之間的a[j]已經輸入過了,那么毫無疑問a[j]>a[i],且a[j]先於a[i]加入樹家庭,說明這就是一個a[i] < a[j](j>i)是一個逆序對

4、在求出m=0(即初始狀況下的逆序對數)后,就開始求變換后的序列的逆序對

  • 簡單啊,線段樹不需要更新了,只需要每次把第一位放序列最后,循環n次。
  • 這么理解:把第一個數放在序列最后面,那么逆序對數會增加也會減少,增加的是從2~n-1之間大於a[1]的個數(即n-1-a[1]),減少的是2~n-1之間小於a[1]的個數(即a[i])

最好畫出線段樹,單點一個一個的更新、查詢嘗試

AC代碼

#include<iostream>
using namespace std;

const int N = 5000 5;

int a[N];

struct node{
    int l;
    int r;
    int v;
    int m(){
        return (l r)/2;
    }
};

struct Seg{
    node tree[N*4];
    void build(int i,int l,int r){
        tree[i].l = l;
        tree[i].r = r;
        tree[i].v = 0;
        if(l != r){
            int m = tree[i].m();
            build(i*2,l,m);
            build(i*2 1,m 1,r); 
        }
    }

    void update(int p,int i){
        int l = tree[i].l;
        int r = tree[i].r;
        if(l==r) tree[i].v    ;
        else{
            int m = tree[i].m();
            if(p<=m) update(p,i*2);
            else update(p,i*2 1);
            tree[i].v = tree[i*2].v   tree[i*2 1].v; 
        }
    }

    int query(int i,int l,int r){
        int li = tree[i].l;
        int ri = tree[i].r;
        if(l<=li && ri<=r) return tree[i].v;
        else{
            int m = tree[i].m();
            int s1 = 0;
            int s2 = 0;
            if(l<=m) s1 = query(i*2,l,r);
            if(r>m) s2 = query(i*2 1,l,r);
            return s1 s2;
        }
    }
}seg;

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int sum=0;
        seg.build(1,0,n-1);
        for(int i=1;i<=n;i  ){
            scanf("%d",&a[i]);
            seg.update(a[i],1);
            if(a[i]!=n-1) sum =seg.query(1,a[i] 1,n-1);
        }
        int mi = sum;
        for(int i=1;i<=n;i  ){
            sum-=a[i];
            sum =n-1-a[i];
            mi = min(mi,sum);
        }
        printf("%d\n",mi);
    }
    return 0;
} 

最佳答案:

DABAN RP主题是一个优秀的主题,极致后台体验,无插件,集成会员系统
U19学习网站 » HDU 1394 Minimum Inversion Number(單點更新) -开发者知识库