当前位置：首页 > news >正文

[HDOJ4911]Inversion

news 来源：原创 2024/4/27 4:55:57

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4911

求经过k次交换后的逆序数对数。

归并排序解法：用该数列的逆序对数减去k，如果大于0则答案就是这个差，否则就是0。（根据逆序对的性质得到）

代码如下：

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 typedef long long LL;
23 const int maxn = 100010;
24 int num[maxn];
25 LL ans;
26 int n, k;
27 
28 void merge(int p, int m, int q) {
29     static int ll[maxn>>1], rr[maxn>>1];
30     int n1 = m - p + 1;
31     int n2 = q - m;
32     for(int i = 0; i < n1; i++)    ll[i] = num[p+i];
33     for(int i = 0; i < n2; i++)    rr[i] = num[m+i+1];
34     int i = 0, j = 0;
35     while(i < n1 && j < n2) {
36         if(ll[i] <= rr[j])    num[p++] = ll[i++];
37         else {
38             num[p++] = rr[j++];
39             ans += (n1 - i);
40         }
41     }
42     while(i < n1) num[p++] = ll[i++];
43     while(j < n2) num[p++] = rr[j++];
44 }
45 
46 void mergesort(int p, int q) {
47     if(p < q) {
48         int m = (p + q) >> 1;
49         mergesort(p, m);
50         mergesort(m+1, q);
51         merge(p, m, q);
52     }
53 }
54 
55 int main() {
56     // freopen("in", "r", stdin);
57     while(~scanf("%d %d", &n, &k)) {
58         ans = 0;
59         for(int i = 0; i < n; i++) {
60             scanf("%d", &num[i]);
61         }
62         mergesort(0, n-1);
63         printf("%I64d\n", ans > k ? ans - k : 0);
64     }
65 }