归并排序的经典-求逆序对 - 江上舟摇
source link: https://www.cnblogs.com/LQS-blog/p/16472028.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
归并排序的经典-求逆序对
本来今天poj崩掉了，并且求逆序对也是个很简单的问题，罗黑上的分治的题也都刷完了（其实难得一见上罗黑的练习题上的简单题目），东哥的题又刷不动，打算今天就到这了
但是一想到以前也没有总结过逆序对的求法，写完这个总结在做一道每日一题就休息了；
先认识一下什么是逆序对，举一个例子：
上述写的够清楚了吧（电脑写字很烂，见谅）
归并排序我相信不用多介绍了吧？都相信已经学了，算了，要不概括一下归并排序的核心吧：
归并排序的核心其实就是先将每个元素初始化为子集，两两子集合并，实现内部排序，一直这样处理知道最后剩下一个集合
稍微说一下合并：
要归并两个有序的子序列
例如我们要归并a[]={13,94,99},{34，56}这两个子序列
将i,j分别指向子序列的第一个数，进行一次比较发现a[i]<a[j]，则将a[i]放在辅助数组b中，经过四次比较
最终可得b[]={13,34,56,94,99}
第二次比较
第三次比较
第四次比较
具体来看题目：
http://acm.hdu.edu.cn/showproblem.php?pid=4911
题目大意：
给定一个数组，交换相邻任意两个元素，且不超过k次，求最少的逆序对有多少？
题目分析：当k=0的时候即求原始数组中有多少对逆序对，并且在每次合并中，如果子序列内部是有序的则不存在逆序对；
在合并两个子序列时，若前子序列的元素大于后子序列的元素则产生逆序对，像上面四次合并，并且在每次合并的时候，可能出现不止一对逆序对，
例如在第二次合并的时候，就出现了{34，96}，{34，99}两对逆序对
那分别讨论原始数组中的逆序对cnt，若cnt<=k则说明不够交换k次，即最少逆序对为0对
若cnt>k则说明k次交换都发生在逆序的相邻元素上，则有最少cnt-k对
解题思路：分治法，归并排序
难度评价：易
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define int long long
4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
5 const int N=1e5+10;
6 int a[N];
7 int b[N];
8 int cnt;
9 int n,k;
10 void Merge(int L,int mid,int R)
11 {
12 //归并
13 int i=L;
14 int j=mid+1;
15 int t=0;
16 while(i<=mid&&j<=R)
17 {
18 if(a[i]>a[j])
19 {
20 b[t++]=a[j++];
21 cnt+=mid-i+1;//出现逆序对
22 }
23 else
24 b[t++]=a[i++];
25 }
26 //检查
27 //一个子序列中的数都处理完了，另一个还没有，把剩下的复制过来
28 while(i<=mid)
29 b[t++]=a[i++];
30 while(j<=R)
31 b[t++]=a[j++];
32 //数组拷贝
33 for(int i=0;i<t;i++)
34 a[L+i]=b[i];
35 }
36 void mergesort(int low,int high)
37 {
38 if(low<high)
39 {
40 int mid=(low+high)/2;
41 //分
42 mergesort(low,mid);
43 mergesort(mid+1,high);
44 //治
45 Merge(low,mid,high);
46 }
47 }
48 signed main()
49 {
50 IOS;
51 while(cin>>n>>k)
52 {
53 cnt=0;
54 for(int i=0;i<n;i++)
55 {
56 cin>>a[i];
57 }
58 mergesort(0,n-1);
59 if(cnt<=k)
60 cout<<0<<endl;
61 else
62 cout<<cnt-k<<endl;
63 }
64 }
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK