HDU 1394 Minimum Inversion Number

Problem Description

The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.

For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:

a1, a2, ..., an-1, an (where m = 0 - the initial seqence)

a2, a3, ..., an, a1 (where m = 1)

a3, a4, ..., an, a1, a2 (where m = 2)

...

an, a1, a2, ..., an-1 (where m = n-1)

You are asked to write a program to find the minimum inversion number out of the above sequences.

Input

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.

Output

For each case, output the minimum inversion number on a single line.

Sample Input

10

1 3 6 9 0 8 5 7 4 2

Sample Output

16

数组可以循环，问最少的逆序对数量是多少。

求出初始情况下的逆序对数量，每次把第一个数移到最后，其实改变的逆序对数之和是n-1对。

树状数组

#include<iostream>  
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 5005;
const int low(int x){ return (x&-x); }
int A[maxn], n, tot, i, j, f[maxn], k, minn;

void add(int x, int y)
{
  for (int i = x; i <= n; i += low(i)) f[i] += y;
}

int sum(int x)
{
  int t = 0;
  for (int i = x; i > 0; i -= low(i)) t += f[i];
  return t;
}

int main(){
  while (~scanf("%d", &n))
  {
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++)
    {
      scanf("%d", &A[i]);
      A[i + n] = ++A[i];
    }
    tot = 0; minn = maxn * maxn;
    for (int i = 1; i < 2 * n; i++)
    {
      if (i <= n) add(A[i], 1);
      k = sum(n) - sum(A[i]);
      if (i <= n) tot += k; else {
        tot = tot + 2 * k - n + 1;
        minn = min(tot, minn);
      }
    }
    cout << minn << endl;
  }
  return 0;
}      

zkw线段树

#include<iostream>  
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 10001;
int n, a[maxn], f[2 * maxn], M, sum, m;

void change(int x, int y)
{
  x += M;   f[x] = y;
  for (x >>= 1; x; x >>= 1) f[x] = f[x + x] + f[x + x + 1];
}

int find(int l, int r)
{
  int tot = 0;
  for (l += M - 1, r += M + 1; l ^ r ^ 1; l >>= 1, r >>= 1)
  {
    if (~l & 1) tot += f[l ^ 1];
    if ( r & 1) tot += f[r ^ 1];
  }
  return tot;
}

int main(){
  while (~scanf("%d", &n))
  { 
    memset(f, 0, sizeof(f));
    for (sum = 0, M = 1; M < n; M += M);
    for (int i = 1; i <= n; i++) 
    { 
      scanf("%d", &a[i]); change(++a[i], 1);
      m = sum += a[i] - find(1, a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
      sum = sum + n + 1 - a[i] - a[i];
      m = min(m, sum);
    }
    cout << m << endl;
  }
  return 0;
}