分治算法小总结 x
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了分治算法小总结 x，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3240字，纯文字阅读大概需要5分钟。
内容图文
其实这个题用冒泡排序做的，但用归并排序也能做出来（分析一下此题与逆序对是有相同之处的）
由于两者的代码完全一样，就只放一个啦 ~\(≧▽≦)/~啦啦啦
1.洛谷 P1116 车厢重组
题目描述
在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。
输入输出格式
输入格式：
输入文件有两行数据，第一行是车厢总数N（不大于10000），第二行是N个不同的数表示初始的车厢顺序。
输出格式：
一个数据，是最少的旋转次数。
输入输出样例
4 4 3 2 1
/*----------------------分割线---------------------*/
2.洛谷 P1908 逆序对
题目描述
猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。
输入输出格式
输入格式：
第一行，一个数n，表示序列中有n个数。
第二行n个数，表示给定的序列。
输出格式：
给定序列中逆序对的数目。
输入输出样例
6 5 4 2 6 3 1
11
说明
对于50%的数据，n≤2500
对于100%的数据，n≤40000。
思路：
代码酱来也~
#include<iostream> #include<algorithm> #define M 111111 usingnamespace std; int n,ans; int a[M],b[M]; void merge_sort(int l,int r) { if(l == r) return; int m = (l+r) / 2 ;//中间值 merge_sort(l,m);//左边 merge_sort(m+1,r); //右边int i=l,j=m+1,k=l; for(;i<=m&&j<=r;) { if(a[i]<=a[j]) b[k++]=a[i++]; else { ans+=m-i+1;//统计产生逆序对的个数 b[k++]=a[j++]; } } for(;i<=m;b[k++]=a[i++]); for(;j<=r;b[k++]=a[j++]); for(int i=l;i<=r;i++) a[i]=b[i]; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; merge_sort(1,n); cout<<ans; return0; }
/*----------------------分割线---------------------*/
3.Codevs 1688 求逆序对
给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目
数据范围：N<=105。Ai<=105。时间限制为1s。
第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。
所有逆序对总数.
4
3
2
3
2
3
代码酱来也~
#include<iostream> #include<algorithm> #define M 111111 #define LL long long usingnamespace std; LL ans; int n; int a[M],b[M]; void merge_sort(int l,int r) { if(l == r) return; int m = (l+r) / 2 ;//中间值 merge_sort(l,m);//左边 merge_sort(m+1,r); //右边int i=l,j=m+1,k=l; for(;i<=m&&j<=r;) { if(a[i]<=a[j]) b[k++]=a[i++]; else { ans+=(LL)m-(LL)i+1; //统计产生逆序对的个数 b[k++]=a[j++]; } } for(;i<=m;b[k++]=a[i++]); for(;j<=r;b[k++]=a[j++]); for(int i=l;i<=r;i++) a[i]=b[i]; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; merge_sort(1,n); cout<<ans; return0; }
4.洛谷 P1115 最大子段和
题目描述
给出一段序列，选出其中连续且非空的一段使得这段和最大。
输入输出格式
输入格式：
输入文件maxsum1.in的第一行是一个正整数N，表示了序列的长度。
第2行包含N个绝对值不大于10000的整数A[i]，描述了这段序列。
输出格式：
输入文件maxsum1.out仅包括1个整数，为最大的子段和是多少。子段的最小长度为1。
输入输出样例
7 2 -4 3 -1 2 -4 3
4
说明
【样例说明】2 -4 3 -1 2 -4 3
【数据规模与约定】
对于40%的数据，有N ≤ 2000。
对于100%的数据，有N ≤ 200000。
思路:
这道题真的就是一道模板题，但是为什么我交了好几遍就是没有AC呢？原因出在第二个点上，因为第二个点里的数据似乎全部都是负的，所以在进行初始化的时候需要赋值为一个极小数(ans,lmax,rmax这三个)，不然按一般的话，一定是从0开始，所以负数就出不来，所以……
代码酱来也~
内容总结
以上是互联网集市为您收集整理的分治算法小总结 x全部内容，希望文章能够帮你解决分治算法小总结 x所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。