题目描述
Description
bobo has a sequence $a_1$,$a_2$,…,$a_n$. 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≤i
Input
The input consists of several tests. For each tests:
The first line contains 2 integers n,k (1≤n≤$10^5$,0≤k≤$10^9$). The second line contains n integers a1,a2,…,an (0≤$a_i$≤$10^9$).
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
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
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;
}