设为首页 加入收藏

TOP

HDU 1394 Minimum Inversion Number 树状数组&&线段树
2015-07-24 05:46:55 来源: 作者: 【大 中 小】 浏览:5次
Tags：HDU 1394 Minimum Inversion Number & 线段

题目给了你一串序列，然后每次 把最后一个数提到最前面来，直到原来的第一个数到了最后一个，每次操作都会产生一个新的序列，这个序列具有一个逆序数的值，问最小的你逆序数的值为多少


逆序数么 最好想到的是树状数组，敲了一把很快，注意把握把最后一个数提上来对逆序数的影响即可，



#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define ll long long #define LL __int64 #define eps 1e-8 #define inf 0xfffffff //const LL INF = 1LL<<61; using namespace std; //vector
                
                  > G; //typedef pair
                 
                   P; //vector
                  
                    > ::iterator iter; // //map
                   
                    mp; //map
                    
                     ::iterator p; int n; int c[10000 + 5]; int num[10000 + 5]; void init() { memset(c,0,sizeof(c)); memset(num,0,sizeof(num)); } int lowbit(int x) { return x&(-x); } void add(int i,int val) { while(i <= n) { c[i] += val; i += lowbit(i); } } int get_sum(int i) { int sum = 0; while(i > 0) { sum += c[i]; i -= lowbit(i); } return sum; } int main() { while(scanf("%d",&n) == 1) { init(); int ans = 0; for(int i=1;i<=n;i++) { scanf("%d",&num[i]); num[i]++; add(num[i],1); ans += (i - get_sum(num[i])); } int minn = ans; for(int i=n;i>1;i--) { ans = ans + num[i] + num[i] - n - 1; minn = min(ans,minn); } printf("%d\n",minn); } return 0; }

线段树： 



#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define ll long long #define LL __int64 #define eps 1e-8 #define inf 0xfffffff //const LL INF = 1LL<<61; using namespace std; //vector
                
                  > G; //typedef pair
                 
                   P; //vector
                  
                    > ::iterator iter; // //map
                   
                    mp; //map
                    
                     ::iterator p; const int N = 10000 + 5; int num[N]; typedef struct Node { int a; int l,r; }; Node tree[N * 4]; void init() { memset(tree,0,sizeof(tree)); memset(num,0,sizeof(num)); } void cal(int id) { tree[id].a = min(tree[id<<1].a,tree[id<<1|1].a); } void build(int l,int r,int id) { tree[id].l = l; tree[id].r = r; tree[id].a = 0; if(l == r) return ; int mid = (l + r)/2; build(l,mid,id<<1); build(mid+1,r,id<<1|1); } void updata(int w,int id) { if(tree[id]. l == w && tree[id].r == w) { tree[id].a = 1;return; } int mid = (tree[id].l + tree[id].r)/2; if(w <= mid) updata(w,id<<1); else updata(w,id<<1|1); tree[id].a = tree[id<<1].a + tree[id<<1|1].a; } int query(int l,int r,int id) { if(l <= tree[id].l && r >= tree[id].r)return tree[id].a; int mid = (tree[id].l + tree[id].r)/2; int ans1 = 0,ans2 = 0; if(l <= mid) ans1 = query(l,r,id<<1); if(r > mid) ans2 = query(l,r,id<<1|1); return ans1 + ans2; } int main() { int n; while(scanf("%d",&n) == 1) { init(); build(1,n,1); int ans = 0; for(int i=0;i
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：CodeForces 20B Equation 水题 下一篇：Autodesk FBX SDK Program 中文 (..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: