NOIP基础算法——贪心和分治pascal

NOIP基础算法——分治与贪心巴蜀中学 黄新军

http://www.77cn.com.cn:8080/bsoi

第四部分 分治策略

一、分治思想 分治(pide-and-conquer)就是“分而治 之”的意思，其实质就是将原问题分成n个 规模较小而结构与原问题相似的子问题； 然后递归地解这些子问题，最后合并其结 果就得到原问题的解。

二、分治法的适用条件 能使用分治法解决的问题，它们一般具备以下几个特征： ①该问题可以分解成若干相互独立、规模较小的相同子问 题； ②子问题缩小到一定的程度就能轻易得到解； ③子问题的解合并后，能得到原问题的解； 分治法在信息学竞赛中应用非常广泛，使用分治策略能生 成一些常用的算法和数据结构，如快排、最优二叉树、线 段树等；还可以直接使用分治策略，解决一些规模很大、 无法直接下手的问题。

三、分治的三步骤 ①分解：将要解决的问题分解成若干个规 分解： 模较小的同类子问题； ②解决：当子问题划分得足够小时，求解 解决： 出子问题的解。 ③合并：将子问题的解逐层合并成原问题 合并： 的解。

分治算法设计过程图

由分治法所得到的子问题与原问题具有相同的类型。如果 得到的子问题相对来说还太大，则可反复使用分治策略将 这些子问题分成更小的同类型子问题，直至产生出不用进 一步细分就可求解的子问题。分治求解可用一个递归过程 来表示。 要使分治算法效率高，关键在于如何分割？一般地，出于 一种平衡原则，总是把大问题分成K个规模尽可能相等的 子问题，但也有例外，如求表的最大最小元问题的算法， 当n=6时，等分定量成两个规模为3的子表L1和L2不是最 佳分割。一般来讲，都是2分为主。

四、分治的框架结构procedure DIVIDE() begin if(问题不可分 问题不可分)then//解决 问题不可分 解决 begin 直接求解； 直接求解； 返回问题的解； 返回问题的解； end else begin 对原问题进行分治； 分解 对原问题进行分治；//分解 递归对每一个分治的部分求解; 递归对每一个分治的部分求解 归并整个问题，得出全问题的解;//合并 归并整个问题，得出全问题的解 合并 end end;

五、分治的典型应用 1、求最大值和最小值 2、非线性方程求根 3、二分查找 4、归并排序 5、快速幂 6、求解线性递推关系 7、棋盘覆盖问题 8、循环日程表问题 9、寻找最近点对

1、求最大值和最小值 例题1:给n个实数，求它们之中最大值和最小值，要求 例题1 个实数，求它们之中最大值和最小值， 比较次数尽量小。 比较次数尽量小。 分析： 分析：假设数据个数为n,存放

在数组a[1..n]中。可以直接进 行比较： minn:=a[1];maxx:=a[1]; for i:=2 to n do if a[i]>maxx then maxx:=a[i]; else if a[i]<minn then minn:=a[i]; 使用这一算法，比较次数为2(n-1)。若n=10,则比较18次。

用分治法解决这个问题就是把集合a分成a1,a2两个子集， 每个子集有n/2个元素，应用递归结构找出两个子集的最 大元和最小元，比较得到的两个最大元和最小元即可得到 整个集合a中的最大元和最小元。 划分：把n个数均分为两半。即：划分点为d=(r1+r2)/2, 划分： 两个区间为[r1,d]和[d+1,r2]。 递归求解：求左半的最小值min1 和最大值max1以及右半 递归求解： 最小值min2和最大值max2。 合并：所有数的最大值为maxx,最小值为minn。 合并：

procedure pd(r1,r2:integer;var maxx,minn:integer) begin var max1,min1,max2,min2,d:integer; if r1=r2 then begin maxx:=x[r1]; minn:=x[r1];end else if r2=r1+1 then begin if x[r2]>x[r1] then begin maxx:=x[r2];minn:=x[r1];end else begin maxx:=x[r1];minn:=x[r2];end end else begin d:=(r1+r2)/2; pd(r1,d,max1,min1); pd(d+1,r2,max2,min2); if max1>max2 then maxx:=max1;else maxx:=max2; if min1<min2 then minn:=min1;else minn:=min2; end end

【思考试题】最大值最小化 思考试题】 【问题描述】把一个包含n个正整数的序列划分成m个连 问题描述】 续的子序列(每个正整数恰好属于一个序列)。设第i个序列 的各数之和为S(i),你的任务是让所有的S(i)的最大值尽 量小。例如序列1 2 3 2 5 4划分成3个序列的最优方案为1 2 3|2 5|4,其中S(1)=6,S(2)=7,S(3)=4,最大值为7; 如果划分成1 2|3 2|5 4,则最大值为9;不如刚才的好。 n<=10^6,所有数字之和不超过10^9。

2、非线性方程求根例题2: 例题 ：一元三次方程的解 题目描述】 【题目描述】有形如：ax3+bx2+cx+d=0这样的一个一元三次 方程。给出该方程中各项的系数(a,b,c,d均为实数),并约定该 方程存在三个不同实根(根的范围在-100至100之间),且根与 根之差的绝对值>=1。要求由小到大依次在同一行输出这三个 实根(根与根之间留有空格),并精确到小数点后4位。 文件输入】 【文件输入】输入仅一行，有四个数，依次为a、b、c、d 文件输出】 【文件输出】输出也只有一行，即三个根(从小到大输出) 样例输入】 【样例输入】1 -5 -4 20 样例输入】 【样例输入】-2.00 2.00 5.00

分析 如果精确到小数点后两位，可用简单枚举法：将x从100.00 到100.00(步长0.01)逐一枚举，得到20000个 f(x),取其值与0最接近的三个f(x),对应的x即为答案。而 题目已改成精度为小数点后4位，枚举算法时间复杂度将 达不到要求。 直接使用求根公式，极为复杂。加上本题的提示给我们以 启迪：采用二分法逐渐缩小根的范围，从而得到根的某精 度

的数值