HDU 1394Minimum Inversion Number（线段树）-白红宇

HDU 1394Minimum Inversion Number（线段树）

阅读量：5747 次

发布时间：2019-06-18

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

题目大意是说给你一个数组(N个)，没戏可以将其首部的k(k<N)个元素移动至尾部，这样总共会形成N个序列

现在要求这n个序列中逆序对数最少的那一个序列有多少个逆序对

最初的确是没太多思路，就算知道线段书可以球某一个序列的逆序对数，但是这里要求n次，就没有太多把握了

而最后的方法其实的确是只用求一次的，由于给出的n个数字是0～n-1的一个排列，所以考虑吧a[0]放到最后一个位置时，那以它作为起点的逆序对数相应的会减少a[0]个(这是因为塔处在地一个位置，所有比它晓得数都会在其后方)，然后考虑a[0]已经被移动到最后一个位置，那么相应的这个序列的逆序对数会增加n-a[0]个

所以只要在一遍线段书或树状数组求出开始时的逆序对数后，后面的可以由它递推得到

1 #include  2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 using namespace std;15 #define INF 1e916 #define inf (-((LL)1<<40))17 #define lson k<<1, L, mid18 #define rson k<<1|1, mid+1, R19 #define mem0(a) memset(a,0,sizeof(a))20 #define mem1(a) memset(a,-1,sizeof(a))21 #define mem(a, b) memset(a, b, sizeof(a))22 #define FOPENIN(IN) freopen(IN, "r", stdin)23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)24 template
                  
                    T CMP_MIN(T a, T b) { return a < b; }25 template
                   
                     T CMP_MAX(T a, T b) { return a > b; }26 template
                    
                      T MAX(T a, T b) { return a > b ? a : b; }27 template
                     
                       T MIN(T a, T b) { return a < b ? a : b; }28 template
                      
                        T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }29 template
                       
                         T LCM(T a, T b) { return a / GCD(a,b) * b; }30 31 typedef __int64 LL;32 //typedef long long LL;33 const int MAXN = 5005;34 const int MAXM = 100005;35 const double eps = 1e-10;36 const LL MOD = 1000000007;37 38 int c[MAXN], a[MAXN], id[MAXN], N;39 40 int lowbit(int x)41 {42 return x & (-x);43 }44 45 void update(int k, int x)46 {47 while(k <= N)48 {49 c[k] += x;50 k += lowbit(k);51 }52 }53 54 int getSum(int k)55 {56 int sum = 0;57 while(k > 0)58 {59 sum += c[k];60 k -= lowbit(k);61 }62 return sum;63 }64 65 int cmp(int i, int j)66 {67 return a[i] > a[j];68 }69 70 int getCnt()71 {72 for(int i=1;i<=N;i++) id[i] = i;73 sort(id+1, id + N + 1, cmp);74 mem0(c);75 int cnt = 0;76 for(int i=1;i<=N;i++)77 {78 cnt += getSum(id[i]);79 update(id[i], 1);80 }81 return cnt;82 }83 84 int main()85 {86 while(scanf("%d", &N) == 1)87 {88 for(int i=1;i<=N;i++) scanf("%d", &a[i]);89 int ans = getCnt(), x = ans;90 for(int i=1;i

转载于:https://www.cnblogs.com/gj-Acit/p/3884639.html

你可能感兴趣的文章