Minimum Inversion Number 数状数组

Minimum Inversion Number

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit Status Practice HDU 1394

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

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5
 6 int n,c[5050];
 7
 8 int lowbit(int x)
 9 {
10     return x&(-x);
11 }
12
13 void add(int i,int val)
14 {
15     while(i<=n)
16     {
17         c[i]=c[i]+val;
18         i=i+lowbit(i);
19     }
20 }
21
22 int sum(int i)
23 {
24     int s=0;
25     while(i)
26     {
27         s=s+c[i];
28         i=i-lowbit(i);
29     }
30     return s;
31 }
32
33 int main()
34 {
35     int i,j,k;
36     int a[5050];
37     while(scanf("%d",&n)!=EOF)
38     {
39         int cnt=0;
40         memset(c,0,sizeof(c));
41         for(i=1;i<=n;i++)
42         {
43             scanf("%d",&a[i]);
44             a[i]++;
45             cnt=cnt+sum(n)-sum(a[i]);
46             add(a[i],1);
47         }
48         int mi=cnt;
49         for(i=1;i<n;i++)
50         {
51             cnt=cnt-(a[i]-1)+(n-a[i]);
52             if(cnt<mi)
53                 mi=cnt;
54         }
55         printf("%d\n",mi);
56     }
57     return 0;
58 }

时间: 08-18

Minimum Inversion Number 数状数组的相关文章

[hdu1394]Minimum Inversion Number(树状数组)

Minimum Inversion Number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 18395    Accepted Submission(s): 11168 Problem Description The inversion number of a given number sequence a1, a2, ..., a

HDU 1394 Minimum Inversion Number (树状数组求逆序数)

Minimum Inversion Number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13942    Accepted Submission(s): 8514 Problem Description The inversion number of a given number sequence a1, a2, ..., a

HDU 1394 Minimum Inversion Number (树状数组)

依旧是再练习下树状数组的使用: 题目大意:   给出N个数,这些数可以把后面的删掉然后放到最前面形成新的序列 可得到的N种情况,求出这N种情况哪种的逆序数最小 解题思路:   先求出第一个序列的逆序数,然后用很巧妙的办法求下一个序列的逆序数,直到全部求出 序列 4 5 2 1 3 6 ,此序列的逆序数为7,它等到的下一个序列为 5 2 1 3 6 4 看这个新序列的产生过程,首部删除4,尾部添加4 删除4,必然会使得这个序列的逆序数减少(4-1)个,因为4前面必定有4-1个数小于4 添加4,必然

hdu 1394 Minimum Inversion Number (裸树状数组 求逆序数)

题目链接 题意: 给一个n个数的序列a1, a2, ..., an ,这些数的范围是0-n-1, 可以把前面m个数移动到后面去,形成新序列: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)求这些序列中,逆序数最少的

hdu 1394 Minimum Inversion Number 逆序数/树状数组

Minimum Inversion Number Time Limit: 1 Sec  Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=1394 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

Minimum Inversion Number 【线段数】

Problem DescriptionThe 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

hdu 1394 Minimum Inversion Number

题目链接:hdu 1394 Minimum Inversion Number 该题是求最小逆序对的扩展.可以使用树状数组来实现.对于$n$个数的序列$A$,其第$i$个数($i\in [0,n)$)的逆序数$r_i$可以表示为它的角标$i$减去在它之前且不大于它的数的个数.例如对序列A = {1,3,5,9,0,8,5,7,4,2}中的数,A[8] = 4.其逆序数$r_8 = 8 - 3 = 5$,第二个3表示三个在它前面且比它小的数:{1,3,0}.从而我们可以得到第$i$个数的逆序数公式:

hdu1394 [Minimum Inversion Number]

Minimum Inversion Number 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 e

HDU 1394 Minimum Inversion Number(线段树求最小逆序数对)

HDU 1394 Minimum Inversion Number(线段树求最小逆序数对) ACM 题目地址:HDU 1394 Minimum Inversion Number 题意: 给一个序列由[1,N]构成,可以通过旋转把第一个移动到最后一个. 问旋转后最小的逆序数对. 分析: 注意,序列是由[1,N]构成的,我们模拟下旋转,总的逆序数对会有规律的变化. 求出初始的逆序数对再循环一遍就行了. 至于求逆序数对,我以前用归并排序解过这道题:点这里. 不过由于数据范围是5000,所以完全可以用线