分治算法例题.doc

目录1031输油管道问题 1解题思路 1程序代码 11032邮局选址 4解题思路 4程序源代码 41034集合划分2 6解题思路: 6程序源代码: 61033集合划分 8解题思路 8程序源代码 81031输油管道问题解题思路本题目可以分为两个步骤:1、找出主管道得位置;2、根据主管道得位置,计算各个油井到主管道得长度之与。根据题意,设主管道贯穿东西,与y轴平行。而各个子油井则分布在主输油管道得上下两侧。如下图:由上图,其实只需要确定主管道得y坐标,而与各个子油井得x坐标无关!根据猜测,易知:主管道得y坐标就就是所有子油井y坐标得中位数。(可以用平面几何知识证明,略)求中位数得方法可以用排序后取a[(left+right)/2],当然更推荐用书上得线性时间选择算法解决。记求得得主管道为,最后要输出得结果只需要计算:,输出即可。另外要提醒得就是本题多Case。程序代码#include<stdio、h>#include<stdlib、h>voids&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(;start<q;start++) { if(arr[start]<=base) { s[start],arr[++index]); } } s[++index],arr[q]); returnindex;}//快速排序voidqsort(int*arr,intp,intq){ if(p<=q) { intpos=partition(arr,p,q); qsort(arr,p,pos-1); qsort(arr,pos+1,q); }}intarr[10001];intmain(){ intn; //注意多case写法 while(scanf("%d",&n)!=EOF) { //读取数据 for(inti=0;i<n;i++) { //读取y scanf("%d%d",&arr[i],&arr[i]); } //排序 qsort(arr,0,n-1); //取中位数得下标mid,然后计算距离 longlongsum=0; intmid=arr[n/2]; for(inti=0;i<n;i++) { sum+=abs(mid-arr[i]); } printf("%I64d\n",sum); } return0;}1032邮局选址解题思路本题与上一题非常类似,这次就是要找出在居民点中邮局得最佳位置。很容易想到,这次不仅要确定y坐标,还要确定x坐标。类似猜想可以知道,邮局最佳位置应该为:等于所有居民点x坐标得中位数;等于所有居民点y坐标得中位数;分别求中位数得过程与上题类似,不再陈述。最终得计算结果:要求距离之与,输出。程序源代码#include<stdio、h>#include<stdlib、h>#include<algorithm>usingnamespacestd;intx[10000],y[10000];intmain(){ intn; while(scanf("%d",&n)!=E