本来今天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 }