4thweek contest.A 归并排序求逆序数

题目：

bobo has a sequence a ₁,a ₂,…,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<j≤n and a _i>a _j.

分析：

应用二分法排序并记录逆序数k，由于题目一开始输入一个ka,所以交换后的数组的逆序数=k-ka.但需要注意：k和ka的大小问题。具体在代码中解释

Input

The input consists of several tests. For each tests:
The first line contains 2 integers n,ka, (1≤n≤10 ⁵,0≤ka≤10 ⁹). The second line contains n integers a ₁,a ₂,…,a _n (0≤a _i≤10 ⁹).

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

代码及重要步骤分析：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int maxn=100005;
 5 long long a[maxn],b[maxn];
 6 long long k;
 7 
 8 int merge_sort(long long x,long long y) //
 9 {
10     if(x<y)
11     {
12         long long m=(x+y)/2; // 划分
13         merge_sort(x,m);      //递归求解
14         merge_sort(m+1,y);    //递归求解
15         int p=0;
16         int i=x;
17         int j=m+1;
18         while(i<=m && j<=y)
19         {
20             if(a[i]>a[j])
21             {
22                 b[p++]=a[j++];   //从左半数组复制到临时空间
23                 k+=m+1-i;        //记录逆序数k
24             }
25             else
26                 b[p++]=a[i++];   //从右半数组复制到临时空间
27 
28         }
29         while(i<=m)
30             b[p++]=a[i++];
31         while(j<=y)
32             b[p++]=a[j++];
33         for(i=0;i<p;++i)
34             a[x+i]=b[i];      //从辅助空间复制回数组a
35 
36     }
37     return 0;
38 }
39 
40 int main()
41 {
42     long long n,ka;
43     int i;
44     while(scanf("%lld%lld",&n,&ka) !=EOF )  //不要加上&& n

45     {
46         k=0;
47         for(i=0;i<n;i++)
48             scanf("%lld",&a[i]);
49         merge_sort(0,n-1);
50         if(k<=ka)     //如果输入的数组本身就有一定顺序，可能逆序数就会小于需要交换的次数
51           printf("0
");
52         else
53             printf("ll%d
",k-ka);
54     }
55 
56     return 0;
57 }