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
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]);
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 }

[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 逆序数/树状数组

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

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,所以完全可以用线