首页 > 代码库 > HDU 4911 Inversion
HDU 4911 Inversion
Time Limit:1000MS Memory Limit:131072KB 64bit IO Format:%I64d & %I64u
Description
bobo has a sequence a 1,a 2,…,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.
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.
Input
The input consists of several tests. For each tests:
The first line contains 2 integers n,k (1≤n≤10 5,0≤k≤10 9). The second line contains n integers a 1,a 2,…,a n (0≤a i≤10 9).
The first line contains 2 integers n,k (1≤n≤10 5,0≤k≤10 9). The second line contains n integers a 1,a 2,…,a n (0≤a i≤10 9).
Output
For each tests:
A single integer denotes the minimum number of inversions.
A single integer denotes the minimum number of inversions.
Sample Input
3 12 2 13 02 2 1
Sample Output
12
/*归并排序求逆序对对数，然后减去可以交换的次数因为数据范围有10^9，所以逆序对的个数可能超过int类型*/#include <iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n;long long k,ans;int a[100005],b[100005];void work(int l,int mid,int r){ int i=l,j=mid+1; int len=0; while(i<=mid && j<=r) { if (a[i]>a[j]) { b[++len]=a[j++]; ans+=mid-i+1; } else b[++len]=a[i++]; } while(i<=mid) b[++len]=a[i++]; while(j<=r) b[++len]=a[j++]; for(int i=1;i<=len;i++) a[l+i-1]=b[i];}void guibing(int l,int r){ int mid; if (l>=r) return; mid=(l+r)/2; guibing(l,mid); guibing(mid+1,r); work(l,mid,r);}int main(){ while(~scanf("%d%lld",&n,&k)) { ans=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); guibing(1,n); printf("%lld\n",ans-k>0?ans-k:0); } return 0;}
HDU 4911 Inversion
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。