首页 > 代码库 > HDU 4944 逆序数对
HDU 4944 逆序数对
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4911
题意：
给出一个序列，可以相邻的交换k次，求 k 次之后，逆序数对最少是多少；
分析：
可以发现，无论怎么交换之后，总共的逆序数对只会-1，那么结果就是，将这个序列排整齐时，要两两交换的次数-k；题目就转换为求这个序列的逆序数对有多少；
这样的两两交换好像是冒泡排序，冒泡排序是O(n^2)；
正确解法是归并排序；当我们合并两个有序序列时，如果，要将后面的插入到前一个中间，那么这里就有m-i+1个逆序数对；
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 1e5 + 5; 6 7 __int64 cnt,k; 8 int a[maxn],c[maxn]; 9 10 11 void merge(int* a,int first,int mid,int last,int* c) {12 int i = first,j=mid+1;13 int m = mid,n=last;14 int k = 0;15 while(i<=m||j<=n) {16 if(j>n||(i<=m&&a[i]<=a[j])) {17 c[k++] = a[i++];18 }19 else {20 c[k++] = a[j++];21 cnt += (m-i+1);22 }23 }24 for(i=0;i<k;i++)25 a[first+i] = c[i];26 }27 28 void mergeSort(int* a,int first,int last,int* c) {29 if(first<last) {30 int mid = (first+last)/2;31 mergeSort(a,first,mid,c);32 mergeSort(a,mid+1,last,c);33 merge(a,first,mid,last,c);34 }35 }36 37 int main()38 {39 int n;40 while(~scanf("%d%I64d",&n,&k)) {41 for(int i=0;i<n;i++)42 scanf("%d",&a[i]);43 memset(c,0,sizeof(c));44 cnt = 0;45 mergeSort(a,0,n-1,c);46 printf("%lld\n",max(cnt-k,0LL));47 }48 return 0;49 }
HDU 4944 逆序数对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。