HDU 4911 Inversion

发表于   |   分类于   |   0 Comments   |   阅读次数

题目描述

Description

bobo has a sequence a1,a2,…,an. He is allowed to swap two adjacent numbers for no more than k times.

Find the minimum number of inversions after his swaps.

Note: The number of inversions is the number of pair (i,j) where 1≤iaj.

Input

The input consists of several tests. For each tests:

The first line contains 2 integers n,k (1≤n≤105,0≤k≤109). The second line contains n integers a1,a2,…,an (0≤ai≤109).

Output

For each tests:

A single integer denotes the minimum number of inversions.

Sample Input

3 1
2 2 1
3 0
2 2 1

Sample Output

1
2

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4911

解题思路

就是求逆序数，询问的是交换任意两个相邻的元素K次，使逆序数最大，最后输出最大的逆序数。

根据一个神奇的定理：如果逆序数大于0，那么必定存在1 <= i < n使得i和i + 1交换后逆序数减1。假设原逆序数为ans，这样的话，我们就可以得到答案是max(ans - k, 0)。

下面给出了两种做法，一种做法就是归并排序法（算法导论学习1—分治法计算逆序数）：
简单说下如何在归并的过程中，计算逆序数。假设，有一个序列array[p, mid, r]. 其中array[p…mid], array[mid + 1, …, r]已经分别从小到大排好序。下面我们将两个子序列进行归并。
假设当前的右边子序列（array[mid + 1, …, r]）的当前待比较元素下表为right, 左边的为left， 当array[left] <= array[right]时， 这时候没有逆序发生（因为left的数比right的大）；当array[left] > array[right]时，right指向的元素具有逆序数，个数为他之前的所有的数，即mid - left + 1。如此遍历下去，即可得到在归并中得到逆序数。

还有一种方法就是树状数组法：
由于这题的数据特别大，所以在使用树状数组的时候就需要将其离散化，然后再判断每一个元素前面有多少个元素就可以了。

AC代码（归并排序）

202MS/2352K/G++

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
#include <cstdio>
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;

int a[100005], b[100005];
ll ans = 0;
void merge_sort(int s, int t)
{
    int mid = (s + t) >> 1;
    int qb = 1, bn = t - s + 1;
    if (s >= t) return;
    merge_sort(s, mid);
    merge_sort(mid + 1, t);
    int i, j;
    for (i = s, j = mid + 1; i <= mid && j <= t; qb++)
    {
        if (a[i] <= a[j])
        {
            b[qb] = a[i];
            i++;
        }
        else
        {
            b[qb] = a[j];
            ans += mid - i + 1;
            j++;
        }
    }
    //将剩余元素合并
    while (i <= mid)
        b[qb++] = a[i++];
    while (j <= t)
        b[qb++] = a[j++];
    for (i = 1, j = s; i < qb; i++, j++)
        a[j] = b[i];
}

int main()
{
    int n, k;
    while (~scanf("%d%d", &n, &k))
    {
        ans = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", a + i);
        }
        merge_sort(1, n);
        printf("%I64d\n", max(ans - k, 0ll));
    }
    return 0;
}

AC代码（树状数组）

171MS/6280K/G++

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;

int N, K;
const int NV = 1000005;
int a[NV], sub_a[NV], bit[NV];
int lowbit(int x)
{
    return x & (-x);
}

void update(int x, int delta)
{
    for (int i = x; i <= N; i += lowbit(i))
    {
        bit[i] += delta;
    }
}

int query(int k)
{
    int cnt = 0;
    for (int i = k; i > 0; i -= lowbit(i))
    {
        cnt += bit[i];
    }
    return cnt;
}

int main()
{
    while (~scanf("%d%d", &N, &K))
    {
        ll ans = 0;
        memset(bit, 0, sizeof(bit));
        for (int i = 1; i <= N; i++)
        {
            scanf("%I64d", a + i);
            sub_a[i] = a[i];
        }
        //离散化
        sort(sub_a + 1, sub_a + N + 1);
        int pos = unique(sub_a + 1, sub_a + N + 1) - sub_a - 1;
        for (int i = 1; i <= N; i++)
        {
            a[i] = lower_bound(sub_a + 1, sub_a + pos + 1, a[i]) - sub_a;
        }

        for (int i = 1; i <= N; i++)
        {
            update(a[i], 1);
            ans += i - query(a[i]);
        }
        ans = max(ans - K, 0LL);
        printf("%I64d\n", ans);
    }
    return 0;
}