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

NOIP基础算法 分治与贪心 巴蜀中学黄新军 第五部分分治策略 一 分治思想 分治 divide and conquer 就是 分而治之 的意思 其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题 然后递归地解这些子问题 最后合并其结果就得到原问题的解 二 分治法的适用条件 能使用分治法解决的问题 它们一般具备以下几个特征 该问题可以分解成若干相互独立 规模较小的相同子问题 子问题缩小到一定的程度就能轻易得到解 子问题的解合并后 能得到原问题的解 分治法在信息学竞赛中应用非常广泛 使用分治策略能生成一些常用的算法和数据结构 如快排 最优二叉树 线段树等 还可以直接使用分治策略 解决一些规模很大 无法直接下手的问题 三 分治的三步骤 分解 将要解决的问题分解成若干个规模较小的同类子问题 解决 当子问题划分得足够小时 求解出子问题的解 合并 将子问题的解逐层合并成原问题的解 分治算法设计过程图 由分治法所得到的子问题与原问题具有相同的类型 如果得到的子问题相对来说还太大 则可反复使用分治策略将这些子问题分成更小的同类型子问题 直至产生出不用进一步细分就可求解的子问题 分治求解可用一个递归过程来表示 要使分治算法效率高 关键在于如何分割 一般地 出于一种平衡原则 总是把大问题分成K个规模尽可能相等的子问题 但也有例外 如求表的最大最小元问题的算法 当n 6时 等分定量成两个规模为3的子表L1和L2不是最佳分割 一般来讲 都是2分为主 四 分治的框架结构 procedureDIVIDE beginif 问题不可分 then 解决begin直接求解 返回问题的解 endelsebegin对原问题进行分治 分解递归对每一个分治的部分求解 归并整个问题 得出全问题的解 合并endend 五 分治的典型应用 1 求最大值和最小值2 非线性方程求根3 二分查找4 归并排序5 快速幂6 求解线性递推关系7 棋盘覆盖问题8 循环日程表问题9 寻找最近点对 1 求最大值和最小值 例题1 给n个实数 求它们之中最大值和最小值 要求比较次数尽量小 分析 假设数据个数为n 存放在数组a 1 n 中 可以直接进行比较 minn a 1 maxx a 1 fori 2tondoifa i maxxthenmaxx a i elseifa i minnthenminn 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 procedurepd r1 r2 integer varmaxx minn integer beginvarmax1 min1 max2 min2 d integer ifr1 r2thenbeginmaxx x r1 minn x r1 endelseifr2 r1 1thenbeginifx r2 x r1 thenbeginmaxx x r2 minn x r1 endelsebeginmaxx x r1 minn x r2 endendelsebegind r1 r2 2 pd r1 d max1 min1 pd d 1 r2 max2 min2 ifmax1 max2thenmaxx max1 elsemaxx max2 ifmin1 min2thenminn min1 elseminn min2 endend 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中所述的二分法迅速出找出解 如此可求出方程的所有的解 核心参考代码 proceduredivide x1 x2 double Beginvarx0 y0 y1 y2 double x0 x1 x2 div2 y1 cal x1 y2 cal x2 y0 cal x0 if x2 x11 thendivide x1 x0 if y0 y21 thendivide x0 x2 End 3 归并排序 归并排序的基本思想 归并排序充分应用分治算法的策略 通过二分的思想 将n个数最终分成n个单独的有序数列 每个数列中仅有一个数字 再将相邻的两列数据合并成一个有序数列 再重复上面的合并操作 直到合成一个有序数列 按照分治三步法来说 归并过程为 1 划分 把序列分成元素个数相等的两半 2 递归求解 把两半分别排序 3 合并 把两个有序表合成一个有序表 分析 显然 前两部分是很容易完成的 关键在于如何把两个有序表合成一个 每次只需要把两个序列中当前的最小元素加以比较 删除较小元素并加入合并后的新表 核心参考代码 procedureMergeSort left right integer 归并排序beginifleft rightthenexit 只有一个元素mid left right div2 找中间位MergeSort left mid 对左边归并MergeSort mid 1 right 对右边归并i left j mid 1 p left 合并左右while ia j thenbegintemp p a j inc p inc j endelsebegintemp p a i inc p inc i endwhile i mid dobegintemp p a i inc p inc i endwhile j right dobegintemp p a j inc p inc i endfori lefttorightdoa i temp i End 变形1 逆序对数目 例题3 求 逆序对 给定一整数数组A A1 A2 An 若iAj 则就为一个逆序对 例如数组 3 1 4 5 2 的逆序对有 问题是 输入n和A数组 统计逆序对数目 数据范围 1 n 30000 朴素算法 在看完试题以后 我们不难想到一个非常简单的算法 穷举算法 即对数组中任意的两个元素进行判断 看它们是不是构成 逆序对 因此这种算法的时间复杂度为O N2 C 0 fori 1ton 1doforj i 1tondoifa i a j thenc c 1 时间效率不尽如人意 问题出现在哪里呢 分治算法 采用二分法求解 记数列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 thenbegintemp p a j inc p inc j end改为 if a i a j thenbegintot tot mid i 1 temp p a j inc p inc j end 4 二分查找 问题描述 给出从小到大排列的n个不同数a 1 a n 试判断元素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 二分查找的递归实现 functionbsh L r x integer integer Beginvarm integer ifL rexit 1 m L r div2 ifa m xbsh m elseifa m xthenbsh bsh L m 1 x elsebsh bsh m 1 r x End 方法2 二分查找的非递归实现 functionbsh L r x integer integer Beginvarm integer while Lxthenr m 1elseL m 1 endbsh 1 查找不成功End 扩展1 二分查找求下界 即第一次出现的位置functionErfen L r x integer integer beginvarmid integer while L r dobeginmid L r div2 ifx a mid thenr midelseL mid 1 end Erfen L end 扩展2 二分查找求上界 即最后一次出现位置的后一个位置 例题 奇怪的函数 问题描述 使得xx达到或超过n位数字的最小正整数x是多少 文件输入 输入一个正整数n 文件输出 输出使得xx达到n位数字的最小正整数x 变形 查找等值点 问题描述 n个不同整数从小到大排序后放在数组A1 An中 是否存在i 使得Ai i 若存在 试找到此点 5 快速幂 问题描述 计算an k n 109 方法1 朴素算法 每次乘以a 时间复杂度O n functionpower a n integer integer beginvarx integer x 1 fori 1tondox x a power x end 方法2 分治算法 划分 如果n是偶数 考虑x ndiv2 否则考虑x n 1 div2递归求解 计算ax 合并 如果n是偶数 则an ax 2 否则an ax 2 a 方法2 分治算法 根据这个方法很容易写出程序 functionpower a n integer integer Beginifn 0beginpower 1 exit endelseifnmod2 1then n为奇数的情况beginx power a n 1 div2 power x x modk a modk endelsebegin n为偶数的情况x power a ndiv2 power x xmodk end End 方法3 用二进制实现快速幂计算 read a b k 输入三个数t b whilet0dobegininc len c len tmod2 t tdiv2 end 转为二进制s 1 fori lendownto1do 用二分法实现abmodkbegins s smodk ifc i 1thens amodk s modk 如果是奇数 就多乘aend writeln s 输出abmodk 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 朴素算法 肯定超时 procedureFib n integer Beginvari integer f 0 0 f 1 1 fori 2tondof i f i 1 f i 2 End 先复习矩阵乘法 两个2 2矩阵相乘的公式为 可用倍增法在O logn 时间内求出幂 忽略高精度 扩展练习 若f i f i 1 f i 2 f i 3 如何计算求出f n 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得到的 read n m 1 a 1 1 1 h 1 fori 1tondom 2 m 比赛总队数while h m do 从一个球队开始构造beginfori 1tohdo 构造其余三个方阵forj 1tohdobegina i j h a i j h 构造右上角方阵a i h j a i j h 构造左下角方阵a i h j h a i j 构造右下角方阵end h h 2 end 核心参考代码 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 贪心法的特点 1 贪心选择性质 算法中每一步选择都是当前看似最佳的选择 这种选择依赖于已做出的选择 但不依赖于未做的选择 2 最优子结构性质 算法中每一次都取得了最优解 即局部最优解 要保证最后的结果最优 则必须满足全局最优解包含局部最优解 但并不是所有具有最优子结构的问题都可以用贪心策略求解 因为贪心往往是盲目的 需要使用更理性的方法 动态规划 例如 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 其对应的总价值分别是90 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 4 5 9T4 T3 t4 9 7 16T5 T4 t5 16 9 25T6 T5 t6 25 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的箱子中 为了降低运送成本 工厂希望尽量减少箱子的数量 如果有一个好算法 能使箱子的数量降到最低 这将给工厂节省不少的资金 请你编写一个程序 分析 分析 例题4 射击比赛 CEOI1997 我们假设射击的目标是一个由R C 2 R C 1000 个小方格组成的矩形网格 网格中每一列恰有2个白色的小方格和R 2个黑色的小方格 定义网格的行从顶至底编号为1 R 列从左至右编号为1 C 射击者可射击C次 在连续的C次射击中 若每列恰好有一个白色的方格被射中 且不存在无白色方格被射中的行 这样的射击才是正确的 问题是 如果存在正确的射击方法 则要求找到它 例如考虑如下目标 由上图可以看出 在每列中依次射中的行坐标为2 3 1 4 现在要求你编程计算出是否有正确的射击方法 根据题设条件 射击的选择有2C种 符合要求的却很少 要解决问题 还需从正确的射击方法的特征入手 方法1 网络流算法 我们将表示列的点编号为1到C 表示行的点编号为C 1到C R 如果一个白色方格处在第i行第j列 那么从点j向点C i连一条弧 弧的容量为1 再增设一个源点S 从点S往点1到C间各连一条弧 弧的容量为1 又设一个汇点T 从点C 1到点C R向汇点T连一条弧 弧的容量为1 那么从源点S到汇点T求最大流 求出的最大流量即为最多可以射击到的行数 各条流的路线则描述了具体的射击方案 显然 如果用网络流求出的最大流量比R小 则问题无解 否则我们可以根据网络流的结果求出该二分图的具体匹配方案 红色的连线流量为1蓝色的连线流量为0选择的射击格即为 1 3 2 1 3 2 4 4 网络流算法经过优化 时间复杂度可以达到O C n 4C 4R 上述网络流算法虽然可以通过全部数据 但编程复杂度很高 而且极易出错 一不小心就会因为一个小错误影响整个程序 方法二 贪心方法统计所有行包含的白格数从还没有射击格的行中选出一个白格数最少的检查所选的行 1 若所选行的白格数为0 则输出无解 2 否则从所选行的白格中任选一个作为射击格 并将与该格同列的另一个白格所处行的白格数减1返回到第2步 直到所有的行都有射击格 若还有列没有选射击格 则在该列任选一白格作为射击格即可 上面的贪心方法非常高效 时间复杂度为O R C 如果在程序中使用堆优化 时间复杂度将降为O R log2C 空间复杂度是线性的 而且非常容易实现 现在关键的问题就是 如何证明它的正确性 证明 用h i 表示第i行的白格数 如果最开始的时候 min h i 0 第i行已经没有办法找到可作为射击格的白格 那么问题只能无解 min h i 1 那么第i行的这一个白格必须要作为射击格 否则将因第i行没有射击格而造成问题无解 min h i 2 那么在这一行任选一个白格 顶多只会造成剩余行中有一行h值为1 再处理那一行 最多也只会再造成剩余行中有一行h值为1 如此往复 将保持h值为1的行数不超过1行 最后最坏的情况也是造成最后一行的h值为1 继续下去所有行就都已选取了射击格了 因此 如果原问题有解 该贪心方法一定能找到一种正确的方案 由此可以证明 此贪心方法是正确的 确定贪心标准 贪心的经典应用 一 三个区间上的问题1 选择不相交区间问题2 区间选点问题3 区间覆盖问题 二 两个调度问题1 流水作业调度问题2 带限期和罚款的单位时间任务调度 三 Huffman编码 四 最优合并问题 1 选择不相交区间问题 给定n个开区间 ai bi 选择尽量多个区间 使得这些区间两两没有公共点 算法实现 首先按照b1 b2 bn的顺序排序 依次考虑各个活动 如果没有和已经选择的活动冲突 就选 否则就不选 贪心策略 取第一个区间 正确性 如果不选b1 假设第一个选择的是bi 则如果bi和b1不交叉则多选一个b1更划算 如果交叉则把bi换成b1不影响后续选择 例题5 活动安排 设有n个活动的集合E 1 2 n 其中每个活动都要求使用同一资源 如演讲会场等 而在同一时间内只有一个活动能使用这一资源 每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi 且si sj或fj si时 活动i与活动j相容 选择出由互相兼容的活动组成的最大集合 2 区间选点问题 给定n个闭区间 ai bi 在数轴上选尽量少的点 使得每个区间内都至少有一个点 不同区间内含的点可以是同一个 算法 首先按照b1 b2 bn排序 每次标记当前区间的右端点X 并右移当前区间指针 直到当前区间不包含X 再重复上述操作 贪心策略 取最后一个 例题6 种树 NOIP模拟试题 一条街的一边有几座房子 因为环保原因居民想要在路边种些树 路边的地区被分割成块 并被编号为1 n 每个块大小为一个单位尺寸并最多可种一棵树 每个居民想在门前种些树并指定了三个号码b e t 这三个数表示该居民想在b和e之间最少种t棵树 当然 b e 居民必须保证在指定地区不能种多于地区被分割成块数的树 即要求t e b 1 允许居民想种树的各自区域可以交叉 出于资金短缺的原因 环保部门请你求出能够满足所有居民的要求 需要种树的最少数量 样例输入 94142462892352样例输出 5 3 区间覆盖问题 给n个闭区间 ai bi 选择尽量少的区间覆盖一条指定线段 s t 本题的突破口仍然是区间包含和排序扫描 不过先要进行一次预处理 每个区间在 s t 外的部分都应该预先被切掉 因为它们的存在是毫无意义的 在预处理后 在相互包含的情况下 小区间显然不应该考虑 把各区间按照a从小到大排序 若a相同 则b从大到小排序 自动处理掉区间包含 注意 若区间1的起点大于s 则无解 因为其他区间的起点更大 不可能覆盖到s点 否则选择起点在s的最长区间 ai bi 后 新的起点应该设置为bi 并且忽略所有区间在bi之前的部分 就像预处理一样 虽然贪心策略比上题复杂 但是仍然只需要一次扫描 如下图 s为当前有效起点 此前部分已被覆盖 则应该选择区间2 贪心思想 在某个时刻s 找一个满足a i s的b i 的最大值即可 例题7 区间 SD