分治算法例题

1、精选文档目录1031 输油管道问题1解题思路1程序代码11032 邮局选址4解题思路4程序源代码41034 集合划分26解题思路：6程序源代码：61033 集合划分8解题思路8程序源代码81031 输油管道问题解题思路 本题目可以分为两个步骤：1、找出主管道的位置；2、根据主管道的位置，计算各个油井到主管道的长度之和。 根据题意，设主管道贯穿东西，与y 轴平行。而各个子油井则分布在主输油管道的上下两侧。如下图：由上图，其实只需要确定主管道的y 坐标，而与各个子油井的x 坐标无关！根据猜测，易知：主管道的y 坐标就是所有子油井y 坐标的中位数。（可以用平面几何知识证明，略）求中位数的方法可以用排

2、序后取a(left+right)/2，当然更推荐用书上的线性时间选择算法解决。记求得的主管道为，最后要输出的结果只需要计算：，输出即可。另外要提醒的是本题多Case。程序代码#include <stdio.h>#include <stdlib.h>void swap(int &a,int &b)int tmp = a;a = b;b = tmp;/本函数求arrp:q的一个划分i，使arrp:i-1都小于arri，arri+1,q都大于arriint partition(int *arr,int p,int q)int index = p-1,start

3、 = p,base = arrq;for(;start<q;start+)if(arrstart<=base)swap(arrstart,arr+index);swap(arr+index,arrq);return index;/快速排序void qsort(int *arr,int p ,int q)if(p<=q)int pos = partition(arr,p,q);qsort(arr,p,pos-1);qsort(arr,pos+1,q);int arr10001;int main()int n;/注意多case 写法while(scanf("%d&quo

4、t;,&n)!=EOF)/读取数据for(int i=0;i<n;i+)/读取yscanf("%d %d",&arri,&arri);/排序qsort(arr,0,n-1);/取中位数的下标mid，然后计算距离long long sum = 0;int mid = arrn/2;for(int i=0;i<n;i+)sum += abs(mid - arri);printf("%I64dn",sum);return 0;1032 邮局选址解题思路本题和上一题非常类似，这次是要找出在居民点中邮局的最佳位置。很容易想到，这

5、次不仅要确定y 坐标，还要确定x 坐标。类似猜想可以知道，邮局最佳位置应该为：等于所有居民点x坐标的中位数；等于所有居民点y 坐标的中位数；分别求中位数的过程和上题类似，不再陈述。最终的计算结果：要求距离之和，输出。程序源代码#include <stdio.h>#include <stdlib.h>#include <algorithm>using namespace std;int x10000,y10000;int main()int n;while(scanf("%d",&n)!=EOF)/读取x 和y 坐标for(int

6、i=0;i<n;i+)scanf("%d %d",&xi,&yi);/调用STL中的排序算法,分别对x 坐标和y 坐标进行排序sort(x,x+n);sort(y,y+n);/取x，y 坐标的中位数并计算距离int midx = xn/2;int midy = yn/2;long long res = 0;for(int i = 0;i < n;i+)res += abs(midx-xi);res += abs(midy-yi);/ 输出结果printf("%I64dn",res);return 0;1034 集合划分2解题思

7、路：递推公式如下：F (n,m) =m*F (n 1,m) +F (n 1,m 1)F（n，m）表示把n 个元素的集合分为m 个子集，有多少种分法。证明如下：n 个元素的集合可以划分为F(n,m)个不同的由m 个非空子集组成的集合。考虑3 个元素的集合，可划分为 1 个子集的集合：1，2，3 2 个子集的集合：1，2，3，1，3，2，2，3，1 3 个子集的集合：1，2，3F(3,1)=1;F(3,2)=3;F(3,3)=1;如果要求F(4,2)该怎么办呢？A. 往里添一个元素4，得到1，2，3，4B. 往里的任意一个子集添一个4，得到1，2，4，3，1，2，3，4，1，3，4，2，1，3，2

8、，4，2，3，4，1，2，3，1，4F(4,2)=F(3,1)+2*F(3,2)1+2*37推广，得F(n,m)=F(n-1,m-1)+m*F(n-1,m)提醒：由于本题数据范围比较大，需要用64 位长整型即_int64 或者long long。程序源代码：#include <stdio.h>/计算把含有n 个元素的集合分割为m 个子集，有多少种解决方案long long divide(int n,int m)if(m=1 | m=n)return 1;elsereturn divide(n-1,m-1)+m*divide(n-1,m);int main()int n,m;/多ca

9、se 输入while(scanf("%d%d",&n,&m)!=EOF)printf("%I64dn",divide(n,m);return 0;1033 集合划分解题思路假定F（n,m）表示整数n的m划分，则整数n的所有划分是：。提醒：1） 由于本题数据范围比较大，需要用64 位长整型即_int64 或者long long。2） 如果n比较大的话，递归算法计算时间会比较长，最好用动态规划算法实现。程序源代码#include <stdio.h>/计算把含有n 个元素的集合分割为m 个子集，有多少种解决方案long long subset(int n,int m)if(n = m | m = 1)return 1;elsereturn subset(n-1,m-1) + m * subset(n-1,m);int main()int n;while(scan