CC

自然万物都趋向从有序变得无序

0%

Minimum Inversion Number HDU 1394

发表于 更新于 分类于 Valine：

题目链接:点我

题目

    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

题意:

求循环最小逆序对数

思路:

线段树单点更新,区间查询.每次将一个数插入相应节点前,先区间查询这个比这个数大的数的个数,因为他们比这个数先出现而且比这个数大,所以构成逆序对.问题的难点在与如何求循环的逆序对数,假设我们把数字k移到到最后去,那么逆序对增加的个数为比k大的数的个数即:n - k - 1,相应的减少的数的个数为小于k的数的个数,即: k,最后递推即可.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;

int b[5000+10];
int a[20000];

void pushup(int cur){
    a[cur] = a[cur << 1] + a[cur << 1|1];//维护逆序对数的总和
}

void build(int cur, int l, int r){
    a[cur] = 0;
    if(l == r)
        return ;
    int mid = (l + r) >> 1;
    build( cur << 1, l ,mid);
    build( cur << 1|1,mid + 1, r);
}

int quiry(int ll, int rr, int l, int r, int cur){
    if (ll <= l && rr >= r)//如果当前区间在要查询区间内,直接返回.
        return a[cur];
    int mid = (l + r) >> 1;
    int ans=0;
    if (ll <= mid) ans += quiry( ll, rr, l, mid, cur << 1);
    if (rr > mid) ans += quiry( ll , rr, mid+1, r, cur << 1|1);
    return ans;
}

void update(int key, int l, int r, int cur){
    if(l == r){
        a[cur]++;
        return ;
    }
    int mid = (l + r) >> 1;
    if(key <= mid) update( key, l, mid, cur << 1);
    else update( key, mid + 1, r, cur << 1|1);
    pushup(cur);
}

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        build(1,0,n-1);
        int sum = 0;
        for(int i = 0;i < n; ++ i){
            scanf("%d", &b[i]);
            sum += quiry( b[i], n-1, 0, n-1, 1);
            update( b[i], 0 , n-1, 1);
        }
        int ans = sum;
        for(int i = 0; i < n; ++ i){//递推求最小逆序对数
            sum += n - b[i] - b[i] - 1;
            ans = min( ans, sum);
        }
        printf("%d\n", ans);
    }
    return 0;
}