HDU-1394-Minimum Inversion Number-白红宇

HDU-1394-Minimum Inversion Number

阅读量：6331 次

发布时间：2019-06-22

本文共 1640 字，大约阅读时间需要 5 分钟。

链接：https://vjudge.net/problem/HDU-1394

题意：

给一个由0-(n-1)n个值组成的序列。挨个把首位置的值移到最后一位，求每次的逆序对数，找到最小的那个。

思路：

线段树，对每个值加1方便处理,每来一个新值，查询当前比他大的值的数目。

位移时，因为数组由(0-(n-1))组成，所以每次加上后面比他大的数的个数(n-a[i])，再减去后面比他小的(a[i]-1)。

找到每次的最小值即可。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   using namespace std;typedef long long LL;const int MAXN = 5e3 + 10;int segment[MAXN*4];int a[MAXN];void Push_up(int root){ segment[root] = segment[root<<1] + segment[root<<1|1];}void Build(int root, int l, int r){ segment[root] = 0; if (l == r) return ; int mid = (l+r)/2; Build(root<<1, l, mid); Build(root<<1|1, mid+1, r);}void Update(int root, int l, int r, int p){ if (l == r) { segment[root]++; return; } int mid = (l+r)/2; if (p <= mid) Update(root<<1, l, mid, p); else Update(root<<1|1, mid+1, r, p); Push_up(root);}int Query(int root, int l, int r, int ql, int qr){ if (l > qr || r < ql) return 0; if (l >= ql && r <= qr) return segment[root]; int mid = (l+r)/2; int sum = 0; sum += Query(root<<1, l, mid, ql, qr); sum += Query(root<<1|1, mid+1, r, ql, qr); return sum;}int main(){ int n; while (cin >> n) { Build(1, 1, n); int sum = 0; for (int i = 1;i <= n;i++) { cin >> a[i]; a[i]++; int tmp = Query(1, 1, n, a[i]+1, n); sum += tmp; Update(1, 1, n, a[i]); } //cout << sum << endl; int res = sum; for (int i = 1;i <= n;i++) { sum += (n-a[i])-(a[i]-1); //cout << sum << endl; res = min(res, sum); } cout << res << endl; } return 0;}