首页 > 代码库 > hdu 1394 Minimum Inversion Number_归并排序
hdu 1394 Minimum Inversion Number_归并排序
题目链接
题意:给你一个有0--n-1数字组成的序列,然后进行这样的操作,每次将最前面一个元素放到最后面去会得到一个序列,那么这样就形成了n个序列,那么每个序列都有一个逆序数,找出其中最小的一个输出!
思路:可以暴力,树状树状,线段树,归并排序,这里只给出,暴力和归并
//暴力
#include <iostream> #include<cstdio> #include<cstring> using namespace std; #define N 5010 int a[N]; long long sum,ans; int main(int argc, char** argv) { int n,i,k,j,ans; while(scanf("%d",&n)!=EOF){ for(i=0;i<n;i++) scanf("%d",&a[i]); sum=0; for(i=0;i<n;i++){ k=0; for(j=i+1;j<n;j++) if(a[i]>a[j]) k++; sum+=k; } ans=sum; for(i=0;i<n;i++){ sum=sum-a[i]+(n-1)-a[i]; if(ans>sum) ans=sum; } printf("%d\n",ans); } return 0; }
//归并排序
#include <iostream> #include<cstdio> #include<cstring> using namespace std; #define MAXN 5010 int a[MAXN],c[MAXN],x[MAXN],cnt; long long sum,ans; void MergeSort(int l,int r){ int mid,i,j,tmp; if(r>l+1){ mid=(l+r)>>1; MergeSort(l,mid); MergeSort(mid,r); tmp=l; for(i=l,j=mid;i<mid&&j<r;){ if(a[i]>a[j]){ c[tmp++]=a[j++]; cnt+=mid-i; }else c[tmp++]=a[i++]; } if(j<r) while(j<r) c[tmp++]=a[j++]; else while(i<mid) c[tmp++]=a[i++]; for(i=l;i<r;i++) a[i]=c[i]; } } int main(int argc, char** argv) { int n,i,k,j,ans; while(scanf("%d",&n)!=EOF){ cnt=0; for(i=0;i<n;i++){ scanf("%d",&x[i]); a[i]=x[i]; } MergeSort(0,n); ans=cnt; for(i=0;i<n;i++){ cnt=cnt-x[i]+(n-1)-x[i]; if(ans>cnt) ans=cnt; } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。