NOIP基础算法综合-分治与贪心.ppt

NOIP基础算法 分治与贪心 巴蜀中学黄新军 第四部分分治策略 一 分治思想 分治法 又叫分治策略 顾名思义 分而治之 它的基本思想为 对于难以直接解决的规模较大的问题 把它分解成若干个能直接解决的相互独立的子问题 递归求出各子问题的解 再合并子问题的解 得到原问题的解 通过减少问题的规模 逐步求解 能够明显降低解决问题的复杂度 二 分治法的适用条件 能使用分治法解决的问题 它们一般具备以下几个特征 该问题可以分解成若干相互独立 规模较小的相同子问题 子问题缩小到一定的程度能轻易得到解 子问题的解合并后 能得到原问题的解 分治法在信息学竞赛中应用非常广泛 使用分治策略能生成一些常用的算法和数据结构 如快排 最优二叉树 线段树等 还可以直接使用分治策略 解决一些规模很大 无法直接下手的问题 三 分治的三步骤 分解 将要解决的问题分解成若干个规模较小的同类子问题 解决 当子问题划分得足够小时 求解出子问题的解 合并 将子问题的解逐层合并成原问题的解 分治算法设计过程图 分治思想 由分治法所得到的子问题与原问题具有相同的类型 如果得到的子问题相对来说还太大 则可反复使用分治策略将这些子问题分成更小的同类型子问题 直至产生出不用进一步细分就可求解的子问题 分治求解可用一个递归过程来表示 要使分治算法效率高 关键在于如何分割 一般地 出于一种平衡原则 总是把大问题分成K个规模尽可能相等的子问题 但也有例外 如求表的最大最小元问题的算法 当n 6时 等分定量成两个规模为3的子表L1和L2不是最佳分割 一般来讲 都是2分为主 四 分治的框架结构 if 问题不可分 直接求解 返回问题的解 else 对原问题进行分治 递归对每一个分治的部分求解 归并整个问题 得出全问题的解 五 分治的典型应用 1 求最大值和最小值2 非线性方程求根3 二分查找4 归并排序5 快速幂6 求解线性递推关系7 棋盘覆盖问题8 循环日程表问题9 寻找最近点对 1 求最大值和最小值 例题1 给n个实数 求它们之中最大值和最小值 要求比较次数尽量小 分析 假设数据个数为n 存放在数组a 1 n 中 可以直接进行比较 minn a 1 maxx a 1 for i 2 imaxx maxx a i elseif a i minn 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 核心代码 voidpd intr1 intr2 int 思考试题 最大值最小化 问题描述 把一个包含n个正整数的序列划分成m个连续的子序列 每个正整数恰好属于一个序列 设第i个序列的各数之和为S i 你的任务是让所有的S i 的最大值尽量小 例如序列123254划分成3个序列的最优方案为123 25 4 其中S 1 6 S 2 7 S 3 4 最大值为7 如果划分成12 32 54 则最大值为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 420 样例输入 2 002 005 00 分析 如果精确到小数点后两位 可用简单枚举法 将x从 100 00到100 00 步长0 01 逐一枚举 得到20000个f x 取其值与0最接近的三个f x 对应的x即为答案 而题目已改成精度为小数点后4位 枚举算法时间复杂度将达不到要求 直接使用求根公式 极为复杂 加上本题的提示给我们以启迪 采用二分法逐渐缩小根的范围 从而得到根的某精度的数值 分析 A 当已知区间 a b 内有一个根时 用二分法求根 若区间 a b 内有根 则必有f a f b b或f a b 2 0 则可确定根为 a b 2并退出过程 2 若f a f a b 2 0 则必然有f a b 2 f b 0 根在 a b 2 b 中 对此区间重复该过程 执行完毕 就可以得到精确到0 0001的根 分析 B 求方程的所有三个实根所有的根的范围都在 100至100之间 且根与根之差的绝对值 1 因此可知 在 100 99 99 98 99 100 100 100 这201个区间内 每个区间内至多只能有一个根 即 除区间 100 100 外 其余区间 a a 1 只有当f a 0或f a f a 1 0时 方程在此区间内才有解 若f a 0 解即为a 若f a f a 1 0 则可以利用A中所述的二分法迅速出找出解 如此可求出方程的所有的解 核心参考代码 voiddivide doublex1 doublex2 doublex0 y0 y1 y2 x0 x1 x2 2 y1 cal x1 y2 cal x2 y0 cal x0 if x2 x11 divide x1 x0 if y0 y21 divide x0 x2 3 归并排序 归并排序的基本思想 归并排序充分应用分治算法的策略 将n个数分成n个单独的有序数列 每个数列中仅有一个数字 再将相邻的两列数据合并成一个有序数列 每个数列中有2个数 再重复上面的合并操作 直到合成一个有序数列 按照分治三步法来说 归并过程为 1 划分 把序列分成元素个数相等的两半 2 递归求解 把两半分别排序 3 合并 把两个有序表合成一个 分析 显然 前两部分是很容易完成的 关键在于如何把两个有序表合成一个 每次只需要把两个序列中当前的最小元素加以比较 删除较小元素并加入合并后的新表 核心参考代码 inttemp maxn 辅助空间voidMergeSort intleft intright 对区间left right进行归并排序 if left right return 只有一个元素mid left right 2 找中间位MergeSort left mid 对左边归并MergeSort mid 1 right 对右边归并i left j mid 1 p left 合并左右while ia j temp p a j elsetemp p a i while i mid temp p a i while j right temp p a j for i left i right i a i temp i 变形1 逆序对数目 例题 求 逆序对 给定一整数数组A A1 A2 An 若iAj 则就为一个逆序对 例如数组 3 1 4 5 2 的逆序对有 问题是 输入n和A数组 统计逆序对数目 数据范围 1 n 30000 朴素算法 原始的解决方案 双重循环 C 0 Fori 1ton 1doforj i 1tondoifa i a j thenc c 1 时间复杂度为O n2 分治算法 采用二分法求解 记数列a st ed 的逆序对数目为D st ed mid st ed 2 则有 D st ed D st mid D mid 1 ed F st mid ed 其中F st mid ed 表示一个数取自A st mid 令一个数取自A mid 1 ed 的逆序对数目 和归并排序一样 划分和递归求解都好办 关键在于合并 如何求出i在左边 而j在右边的逆序对数目呢 统计的常见技巧是 分类 我们按照j的不同把这些 跨越两边 的逆序对进行分类 只要对于右边的每个j 统计左边比它大的元素个数f j 则所有f j 之和便是答案 幸运的是 归并排序可以帮助我们 顺便 完成f j 的计算 由于合并操作是从小到大进行排序的 当右边的a j 复制到T中时 左边还没有来得及复制到T的那些数就是左边所有比a j 大的数 此时累加器中加上左边元素个数mid i 1即可 即把 if a i a j temp p a j 改为 if a i a j tot tot mid i 1 temp p a j 4 二分查找 问题描述 给出从小到大排列的n个不同数a 0 a n 1 试判断元素x是否出现在表中 方法1 顺序查找 方法是一个个寻找 时间复杂度为O n 这个方法并没有用到 n个数从小到大排列 这一个关键条件 因而时间效率低下 方法2 二分查找 只需要比较log2n个元素 假设需要在a L a r 中查找元素x 划分 检查某个元素a m Lx 那么元素只可能在a L a m 1 中 如果a m x 那么元素只可能在a m 1 a r 中 合并 不需要合并 方法1 二分查找的递归实现 intbsearch intL intr intx if L r return 1 intm L r 2 if a m x returnm elseif a m x returnbsearch L m 1 x elsereturnbsearch m 1 r x 方法2 二分查找的非递归实现 intbsearch intL intr intx intm while Lx r m 1 elseL m 1 return 1 查找不成功 扩展1 二分查找求下界 即第一次出现的位置intErfen intL intr intx intmid while L r mid L r 2 if x a mid r mid elseL mid 1 returnL 扩展2 二分查找求上界 即最后一次出现位置的后一个位置 思考题目 给出n个整数和m个询问 对于每个询问 a b 输出闭区间 a b 内的整数c的个数 思路点拨 先把所有的数据从小到大排序 二分查找求下界 即第一次出现的位置low 二分查找求上界 即最后一次出现位置的后一个位置high 答案区间为 ans high low 变形1 查找等值点 问题描述 n个不同整数从小到大排序后放在数组A0 An 1中 是否存在i 使得Ai i 若存在 试找到此点 5 快速幂 问题描述 计算an k n 109 方法1 朴素算法 每次乘以a 时间复杂度O n intpower inta intn intx 1 for i 1 i n i x a returnx 方法2 分治算法 划分 如果n是偶数 考虑k n 2 否则考虑k n 1 2递归求解 计算ak 合并 如果n是偶数 则an ak 2 否则an ak 2 a根据这个方法很容易写出程序 intpower inta intn if n 0 return1 elseif n 2 1 intx power a n 1 2 return x x k a k else intx power a n 2 return x x k 方法3 用二进制实现快速幂计算 cin b p k 输入三个数t p while t 0 len a len t 2 t t 2 转为二进制ans 1 for i len i 1 i 用二分法实现b pmodk ans ans ans k if a i 1 ans b k ans k 如果是奇数 就多乘b cout ans endl 输出b pmodk 6 求解线性递推关系 例题 Fibonacci数 题目描述 Fibonacci数列定义为 f i f i 2 f i 1 i 2 其中f 1 1 f 2 1 现在请你求Fibonacci数列的第n项 文件输入 输入文件只有一行为一个整数n 1 n 2 31 1 文件输出 输出文件只有一行为一个整数 表示Fibonacci数列的第n项mod32768的值 样例输入 4 样例输出 3 数据范围 对于20 的数据 1 n 1000对于40 的数据 1 n 10000000对于100 的数据 1 n 2 31 1 分析 枚举 肯定超时 voidprecalc fib intn f 0 0 f 1 1 for inti 2 i n i f i f i 1 f i 2 先复习矩阵乘法 两个2 2矩阵相乘的公式为 可用倍增法在O logn 时间内求出幂 忽略高精度 一般情形 7 棋盘覆盖问题 分析 8 循环日程表问题 例题 比赛安排 问题描述 设有2n n 6 个球队进行单循环比赛 计划在2n 1天内完成 每个队每天进行一场比赛 设计一个比赛的安排 使在2n 1天内每个队都与不同的对手比赛 例如n 2时的比赛安排为 队1234比赛1 23 4第一天1 32 4第二天1 42 3第三天 文件输入 一个整数n 文件输出 输出比赛安排表 样例输入 2 样例输出 1 23 41 32 41 42 3 初看此题 感觉无法下手 因为没有任何直接可用的算法和数据结构 仔细分析 可以发现 将问题进行分解 能找出规律 当n 1时 共有2个球队参赛 一天就可以比完 当n 2时 共有4个球队 需比赛3天 从2个球队的比赛安排表中可以看出 左上角与右下角对称 左下角与右上角对称 左下角的值是由左上角值加n得到的 cin n m 1 a 1 1 1 h 1 m 1 n 比赛总队数while h m 从一个球队开始构造 for i 1 i h i for j 1 j h j a i j h a i j h 构造右上角方阵a i h j a i j h 构造左下角方阵a i h j h a i j 构造右下角方阵 h h 2 核心参考代码 9 寻找最近点对 给定平面上n个点 找出其中的一对点的距离 使得在这n个点的所有点对中 该距离为所有点对中最小的 n 60000 分析 问题简述 给定平面上n个点的坐标 找出其中欧几里德距离最近的两个点 方法1 枚举算法 需要枚举O n2 个点对 每个距离的计算时间为O 1 故总的时间复杂度为O n2 有没有更好的算法呢 方法2 分治算法 先按照X坐标排序 把所有点划分成个数尽量相等的两部分 分别求最近点对 设距离分别为dL和dr 合并 令d min dL dr 则跨越两边的点对中 只有下面的竖条中的才有可能更近 需要检查竖条里的所有点对吗 由d的意义可知 P2中任何2个S中的点的距离都不小于d 由此而来可以推出矩形R中最多只有6个d 2 2 3 d的矩形 如下图所示 反证法 若矩形R中有多于6个S中的点 则由鸽笼原理易知至少有一个d 2 2 3 d的小矩形中有2个以上S中的点 设U V是这样2个点 它们位于同一小矩形中 则 X U X V 2 Y U Y V 2 d 2 2 d 2 2 25d2 36因此 D U V 5d 6 d 这与d的意义相矛盾 也就是说矩形R中最多只有6个S中的点 由于这种稀疏性质 对于P1中任一点p P2中最多只有6个点与它构成最接近点对的候选者 第五部分贪心策略 序言 近年来的信息学竞赛中 经常需要求一个问题的可行解和最优解 这就是所谓的最优化问题 贪心法是求解这类问题的一种常用算法 在众多的算法中 贪心法可以算得上是最接近人们日常思维的一种算法 它在各级各类信息学竞赛 尤其在一些数据规模很大的问题中发挥着越来越重要的作用 一 什么是贪心法 贪心法是从问题的某一个初始状态出发 通过逐步构造最优解的方法向给定的目标前进 并期望通过这种方法产生出一个全局最优解的方法 贪心方法的基本思想 贪心是一种解题策略 也是一种解题思想使用贪心方法需要注意局部最优与全局最优的关系 选择当前状态的局部最优并不一定能推导出问题的全局最优利用贪心策略解题 需要解决两个问题 该题是否适合于用贪心策略求解如何选择贪心标准 以得到问题的最优解 引例 在一个N M的方格阵中 每一格子赋予一个数 即为权 规定每次移动时只能向上或向右 现试找出一条路径 使其从左下角至右上角所经过的权之和最大 我们以2 3的矩阵为例 若按贪心策略求解 所得路径为 1 3 4 6 若按动态规划求解 所得路径为 1 2 10 6 适用于贪心策略求解的问题的特点 适用于贪心策略求解的问题必须具有最优子结构的性质 但并不是所有具有最优子结构的问题都可以用贪心策略求解 因为贪心往往是盲目的 需要使用更理性的方法 动态规划 例如 0 1背包问题 与 部分背包问题 问题1 部分背包问题 给定一个最大载重量为M的卡车和N种食品 有食盐 白糖 大米等 已知第i种食品的最多拥有Wi公斤 其商品价值为Vi元 公斤 编程确定一个装货方案 使得装入卡车中的所有物品总价值最大 分析 因为每一个物品都可以分割成单位块 单位块的利益越大 显然总收益越大 所以它局部最优满足全局最优 可以用贪心法解答 方法如下 先将单位块收益按从大到小进行排列 然后用循环从单位块收益最大的取起 直到不能取为止便得到了最优解 问题2 0 1背包问题 给定一个最大载重量为M的卡车和N种动物 已知第i种动物的重量为Wi 其最大价值为Vi 设定M Wi Vi均为整数 编程确定一个装货方案 使得装入卡车中的所有动物总价值最大 分析 按贪心法 有反例 设N 3 卡车最大载重量是100 三种动物A B C的重量分别是40 50 70 其对应的总价值分别是80 100 150 贪心策略与其他算法的区别 1 贪心与递推 与递推不同的是 贪心法中推进的每一步不是依据某一固定的递推式 而是当前看似最佳的贪心决策 不断的将问题归纳为更加小的相似的子问题 所以归纳 分析 选择正确合适的贪心策略 是正确解决贪心问题的关键 2 贪心与动态规划 与动态规划不同的是 贪心是鼠目寸光 动态规划是统揽全局 几个简单的贪心例子 贪心策略 例题1 删数问题 键盘输入一个高精度的正整数n n 240位 去掉其中任意s个数字后剩下的数字按照原来的次序将组成一个新的正整数 编程对给定的n和s 寻求一种方案 使得剩下组成的新数最小 样例输入 1785434 样例输出 13 分析 由于正整数n的有效位数最大可达240位 所以可以采用字符串类型来存储n 那么 应如何来确定该删除哪s位呢 是不是只要删掉最大的s个数字就可以了呢 为了尽可能地逼近目标 我们选取的贪心策略为 每一步总是选择一个使剩下的数最小的数字删去 即按高位到低位的顺序搜索 若各位数字递增 则删除最后一个数字 否则删除第一个递减区间的首字符 然后回到串首 按上述规则再删除下一个数字 重复以上过程s次 剩下的数字串便是问题的解了 例题2 排队问题 在一个食堂 有n个人排队买饭 每个人买饭需要的时间为Ti 请你找出一种排列次序 是每个人买饭的时间总和最小 思路点拨 由题意可知 本题可以采用的贪心策略为 将n个人排队买饭的时间从小到大排序 再依次累加每人的买饭时间 即可得到最小的总和 由样例可知 排好序后的数据为 1 3 5 7 9 11 每个人的买饭时间如下 T1 1T2 T1 T2 1 3 4T3 T2 T3 1 3 5 9T4 T3 t4 1 3 5 7 16T5 T4 T5 1 3 5 7 9 25T6 T5 T6 1 3 5 7 9 11 36总时间T T1 T2 T3 T4 T5 T6 91用反证法证明如下 假设一个不排好序的n个人也能得到最优答案 比如把 1 3 5 7 9 11 中的3 5对调一下 得到的序列为 1 5 3 7 9 11 对调后 3 5前后的1 7 9 11四个人的买饭时间不会有变化 关键的变化是3 5两个人 这时 5这个人的买饭时间为1 5 3这个人的买饭时间变为1 5 3 此时两个人的总买饭时间中 5被累加了2次 而原方案中是3被累加了2次 其他一样 由此 两者相比较 可知有序的序列能得到最优的方案 对于其他位置的改变可以采用同样的方法证明 用反证法证明时 关键是证明反例不成立 由此推出原方案是最优的 问题推广 排队打水问题 有n个人排队到r个水龙头去打水 他们装满水桶的时间t1 t2 tn为整数且各不相等 应如何安排他们的打水顺序才能使他们总共花费的时间最少 例题3 打包 某工厂生产出的产品都要被打包放入正四棱柱的盒子内 所有盒子的高度为h 但地面尺寸不同 可以为1x1 2x2 3x3 4x4 5x5 6x6 如下图所示 这些盒子将被放入高度为h 地面尺寸为6x6的箱子中 为了降低运送成本 工厂希望尽量减少箱子的数量 如果有一个好算法 能使箱子的数量降到最低 这将给工厂节省不少的资金 请你编写一个程序 分析 分析 贪心的经典应用 一 三个区间上的问题1 选择不相交区间问题2 区间选点问题3 区间覆盖问题 二 两个调度问题1 流水作业调度问题2 带限期和罚款的单位时间任务调度 1 选择不相交区间问题 2 区间选点问题 3 区间覆盖问题 1 流水作业调度问题 2 带限期和罚款的单位时间任务调度 贪心方法的推广 贪心与其它算法结合搜索的最优化剪枝 生日蛋糕 优化动态规划 Peter的快餐店 贪心方法与解题策略最优方法不一定是最好方法想不到最优解法就用较优解法 贪心与其它算法结合 例题5 Peter的快餐店 贪心与动态规划 Peter最近在R市新开了一家快餐店 该快餐店准备推出一种套餐 每套由A个汉堡 B个薯条和C个饮料组成 为了提高产量 Peter引进了N条生产线 所有生产线都可以生产汉堡 薯条和饮料 由于每条生产线一天能工作的时间是有限的 不同的 而汉堡 薯条和饮料的单位生产时间又不同 Peter需要知道 怎样安排才能是一天中生产的套餐量最大 假设一天中汉堡 薯条和饮料的产量均不超过100个 且生产线总数小于等于10 贪心与其它算法结合 分析 用p1 p2 p3分别表示汉堡 薯条和饮料的单位生产时间 t i 表示第i条生产线每天的生产时间 p i j k 表示用前i条生产线生产j个汉堡 k个薯条的情况下 最多能生产的饮料数 r i j k 表示用第i条生产线生产j个汉堡 k个薯条的情况下 最多能生产的饮料数 则p i j k max p i 1 j1 k1 r i j j1 k k1 j j1 p1 k k1 p2 t i 通过对该算法的时间复杂度分析 最坏的情况下时间复杂度将达到109 是相当费时的 贪心与其它算法结合 现在加入贪心方法 用贪心方法作预处理 首先计算出一天生产套数的上限值 min 100divA 100divB 100divC 接着 用贪心方法计算出这N条生产线可以生产的套数 并与上限比较 大于或等于则输出上限值并退出 否则再调用动态规划 因为贪心方法的代价很低 这里甚至可以使用多次贪心标准不同的贪心方法 取其最大值 在运行动态规划的过程中 也可以每完成一阶段工作便与上限值进行比较 将贪心思想充分融入到动态规划过程中 这样以来 便可望在动态规划完成前提前结束程序 贪心方法小结 贪心作为一种解题思路 虽然有时无法证明它的正确性 但在无法找到其他算法的时候 不失为一种好方法 并且 贪心与其他算法的结合 可以对其他算法起到优化作用