解1484的一点关键思路。
Minimum Inversion Numberhttp://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;
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)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 小康，你反求第一个序列的逆序数的程序帖出来。让大家学习学习吧 和你们一样
页:
[1]