Java教程

归并排序的经典-求逆序对

本文主要是介绍归并排序的经典-求逆序对,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

 

这篇关于归并排序的经典-求逆序对的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!