HDU 4911 水

本文主要是介绍HDU 4911 水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对于n个数，可以做k次移动，每次移动可以互换相邻位置的两个数，问最少 number of pair (i,j) where 1≤i<j≤n and a_i>a_j.

如果不移动的话，ans=’n个数的逆序对数‘，移动k次会减少k个

归并排序求逆序对数：

#include "stdio.h"
#include "string.h"
#include "math.h"
int b[100010],a[100010],mark[100010];
__int64 k,ans;void merge(int l,int mid,int r)
{int i,j,m;i=l;j=mid+1;m=0;while (i<=mid && j<=r){if (a[i]<=a[j])mark[m++]=a[i++];else{mark[m++]=a[j++];ans+=mid-i+1;}}while (i<=mid)mark[m++]=a[i++];while (j<=r)mark[m++]=a[j++];for (i=0;i<m;i++)a[l+i]=mark[i];
}void mergesort(int l,int r)
{int mid;if (l<r){mid=(l+r)/2;mergesort(l,mid);mergesort(mid+1,r);merge(l,mid,r);}
}int main()
{int n,i,min;while (scanf("%d%d",&n,&k)!=EOF){for (i=0;i<n;i++){scanf("%d",&a[i]);b[i]=a[i];}ans=0;mergesort(0,n-1);ans-=k;if (ans<0) ans=0;printf("%I64d\n",ans);}return 0;
}

这篇关于HDU 4911 水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---