解1484的一点关键思路。

剑乱

Minimum Inversion Number

http://acm.zju.edu.cn/show_problem.php?pid=1457
--------------------------------------------------------------------------------


Time limit: 1 Seconds   Memory limit: 32768K   
题目如下：
Total Submit: 1451   Accepted Submit: 582   

--------------------------------------------------------------------------------

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


Author: CHEN, Gaoli

[ Last edited by 剑乱 on 2005-7-22 at 23:12 ]

剑乱

#include<stdio.h>
int main()
{   int a[5000];
        int min,i,j,n,t;
        freopen(\"in.txt\",\"r\",stdin);
  while(scanf(\"%d\",&n)!=EOF)
  { for(i=0;i<n;i++)
      scanf(\"%d\",&a);
        for(t=0,i=0;i<n;i++)
        {         for(j=i+1;j<n;j++)
                   if(a>a[j])t++;
                min=t;             
        }
        for(i=0;i<n;i++)
        { t=t-2*a+n-1;
      if(min>t)min=t;
        }
    printf(\"%d\\n\",min);   

  }

return 0;
}

小康

你的关键思路是什么啊?

小康

求MIN部分还可以更快,这部分消耗了大部分运行时间,效率是N*N,有一个NLOGN的算法

剑乱

先求出第一个序列的逆序数，然后可以根据第一个序列的逆序数求出第二个序的逆序数，根据第二个序列的逆序数求出第三个序的逆序数，这样把所有的逆序数求出来。就可以把最少的那个逆序数输出来。其中核心代码：
        for(i=0;i<n;i++)
          { t=t-2*a+n-1;
           if(min>t)min=t;
          }
假如求得第一个序列的逆序数为t
                           a1 a2 a3 a4 a5
把5掉到最后，变为a2 a3 a4 a5 a1
                     第二序列的逆序数跟第一序列的逆序数不同的是a1的位置不同。
   第二序列的逆序数比因为5位置的改变而有减少和增加。减少的是比数字a1小的数的个数，也就是a1，增加的是比a1大的数的个数，也就是n-a1+1;所以第二序列的逆序数是t=t-a+n-a-1;如此累推。由于语言表达能力有限，相信位位ACMER看完程序会对我的思路有所了解的了。就不吹了

剑乱

求第一个序列可以用归并排序的思想。这样更快吧

小康

GOOD

剑乱

小康，你反求第一个序列的逆序数的程序帖出来。让大家学习学习吧

小康

和你们一样