首页 > 代码库 > noip2013 火柴排序
noip2013 火柴排序
涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：
，其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。
intput：
4
2 3 1 4
3 2 1 4
output：
1
思路：
先开一个结构体,然后输入。按照v的大小升序排序。
1 const int maxn=100010;2 struct cyc3 {4 int V,id;5 }a[maxn],b[maxn];
然后，将a中元素对应b的的位置储存到c。
最后，归并排序即可。
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<iomanip> 8 #include<queue> 9 using namespace std;10 const int maxn=100010,lln=99999997;11 struct cyc12 {13 int v,id;14 }a[maxn],b[maxn];15 int n;16 int c[maxn],d[maxn];17 int ans=0;18 bool myc(cyc x,cyc y)19 {20 return x.v<y.v;21 }22 void work(int l,int r)23 {24 int mid,tmp,i,j;25 if(l+1<r)26 {27 mid=(l+r)/2;28 work(l,mid-1);29 work(mid,r);30 tmp=l;31 for(i=l,j=mid;i<=mid-1&&j<=r;)32 {33 if(c[i]>c[j])34 {35 d[tmp++]=c[j++];36 ans=1LL*(ans+mid-i)%lln;37 }38 else39 {40 d[tmp++]=c[i++];41 }42 }43 if(j<=r)44 {45 for(;j<=r;j++) d[tmp++]=c[j];46 }47 else48 {49 for(;i<=mid-1;i++) d[tmp++]=c[i];50 }51 for(i=l;i<=r;i++)52 c[i]=d[i];53 }54 else{55 if(l+1==r)56 {57 if(c[l]>c[r])58 {59 swap(c[l],c[r]);60 ans=1LL*(ans+1)%lln;61 }62 }63 }64 }65 int main()66 {67 /*freopen("2.in","r",stdin);68 freopen("2.out","w",stdout);*/69 //ios::sync_with_stdio(false);70 cin>>n;71 for(int i=1;i<=n;i++)72 {73 cin>>a[i].v;74 a[i].id=i;75 }76 for(int i=1;i<=n;i++)77 {78 cin>>b[i].v;79 b[i].id=i;80 }81 sort(a+1,a+1+n,myc);82 sort(b+1,b+1+n,myc);83 for(int i=1;i<=n;i++)84 c[b[i].id]=a[i].id;85 work(1,n);86 cout<<ans<<endl;87 return 0;88 }
noip2013 火柴排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。