分治算法例题.doc

《分治算法例题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、left+right)/2]，当然更推荐用书上的线性时间选择算法解决。记求得的主管道为，最后要输出的结果只需要计算：，输出即可。另外要提醒的是本题多Case。程序代码#include#includevoidswap(int&a,int&b){inttmp=a;a=b;b=tmp;}//本函数求arr[p:q]的一个划分i，使arr[p:i-1]都小于arr[i]，arr[i+1,q]都大于arr[i]intpartition(int*arr,intp,intq){intindex=p-1,start=p,base=arr[q];for(

3、;start

4、取数据for(inti=0;i

5、于所有居民点x坐标的中位数；等于所有居民点y坐标的中位数；分别求中位数的过程和上题类似，不再陈述。最终的计算结果：要求距离之和，输出。程序源代码#include#include#includeusingnamespacestd;intx[10000],y[10000];intmain(){intn;while(scanf("%d",&n)!=EOF){//读取x和y坐标for(inti=0;i

6、序sort(x,x+n);sort(y,y+n);//取x，y坐标的中位数并计算距离intmidx=x[n/2];intmidy=y[n/2];longlongres=0;for(inti=0;i

7、的由m个非空子集组成的集合。考虑3个元素的集合，可划分为①1个子集的集合：{{1，2，3}}②2个子集的集合：{{1，2}，{3}}，{{1，3}，{2}}，{{2，3}，{1}}③3个子集的集合：{{1}，{2}，{3}}∴F(3,1)=1;F(3,2)=3;F(3,3)=1;如果要求F(4,2)该怎么办呢？A.往①里添一个元素{4}，得到{{1，2，3}，{4}}B.往②里的任意一个子集添一个4，得到{{1，2，4}，{3}}，{{1，2}，{3，4}}，{{1，3，4}，{2}}，{{1，3}，{2，4}}，