NOIP中的贪心.pptx

NOIP中的贪心GreedyAlgorithm 贪一贪就有分了哈哈哈 定义 将整个问题分成若干个子问题通过每个子问题的最优解求出整个问题的最优解 是不是soeasy 就像在n m的矩阵中 每行取一个数 使它们的和最大不用说你也知道怎么做但是 你觉得考试有那么裸么 开玩笑 注意 当且仅当每个当前最优解的选择能导出总体最优解 才能用贪心当然 你必须选对拿什么贪 或者说 什么策略搞得像犯罪一样 能贪么 比如0 1背包 肯定不能按单位体积价值去贪心但是部分背包可以我相信你能分清它们如果你分不清 RMB会告诉你 看看题吧 NOIP2002均分纸牌 均分纸牌 问题描述 有N堆纸牌 编号分别为1 2 N 每堆上有若干张 但纸牌总数必为N的倍数 可以在任一堆上取若于张纸牌 然后移动 移牌规则为 在编号为1堆上取的纸牌 只能移到编号为2的堆上 在编号为N的堆上取的纸牌 只能移到编号为N 1的堆上 其他堆上取的纸牌 可以移到相邻左边或右边的堆上 现在要求找出一种移动方法 用最少的移动次数使每堆上纸牌数都一样多 例如N 4 4堆纸牌数分别为 9 8 17 6移动3次可达到目的 从 取4张牌放到 981310 从 取3张牌放到 9111010 从 取1张牌放到 10101010 输入 键盘输入文件名 文件格式 N N堆纸牌 1 N 100 A1A2 An N堆纸牌 每堆纸牌初始数 l Ai 10000 输出 输出所有堆均达到相等时的最少移动次数 是不是想大吼一句 这是贪心 没错这就是 好好想想吧接下来我要第一次试用ppt的SmartArt功能你们先想着 NOIP1999拦截导弹 某国为了防御敌国的导弹袭击 发展出一种导弹拦截系统 但是这种导弹拦截系统有一个缺陷 虽然它的第一发炮弹能够到达任意的高度 但是以后每一发炮弹都不能高于前一发的高度 某天 雷达捕捉到敌国的导弹来袭 由于该系统还在试用阶段 所以只有一套系统 因此有可能不能拦截所有的导弹 输入导弹依次飞来的高度 雷达给出的高度数据是不大于30000的正整数 计算这套系统最多能拦截多少导弹 如果要拦截所有导弹最少要配备多少套这种导弹拦截系统 样例 INPUT38920715530029917015865OUTPUT6 最多能拦截的导弹数 2 要拦截所有导弹最少要配备的系统数 话说这是我们的第一道贪心题当时直接理解错题意然后呵呵所以如果理解对的话 很容易能想到贪心对于每套系统 只需存它拦截的最后一枚导弹的高度如果新的导弹比所有系统能拦截的高度都高 那就再来一套否则选择能拦截该导弹的高度最低的系统代码很容易 不再cv当然 此题也可以动规解决 那就不是我的事情了 NOIP2004合并果子 问题描述 在一个果园里 多多已经将所有的果子打了下来 而且按果子的不同种类分成了不同的堆 多多决定把所有的果子合成一堆 每一次合并 多多可以把两堆果子合并到一起 消耗的体力等于两堆果子的重量之和 可以看出 所有的果子经过n 1次合并之后 就只剩下一堆了 多多在合并果子时总共消耗的体力等于每次合并所耗体力之和 因为还要花大力气把这些果子搬回家 所以多多在合并果子时要尽可能地节省体力 假定每个果子重量都为1 并且已知果子的种类数和每种果子的数目 你的任务是设计出合并的次序方案 使多多耗费的体力最少 并输出这个最小的体力耗费值 例如有3种果子 数目依次为1 2 9 可以先将1 2堆合并 新堆数目为3 耗费体力为3 接着 将新堆与原先的第三堆合并 又得到新的堆 数目为12 耗费体力为12 所以多多总共耗费体力 3 12 15 可以证明15为最小的体力耗费值 输入文件 输入文件fruit in包括两行 第一行是一个整数n 1 n 10000 表示果子的种类数 第二行包含n个整数 用空格分隔 第i个整数ai 1 ai 20000 是第i种果子的数目 输出文件 输出文件fruit out包括一行 这一行只包含一个整数 也就是最小的体力耗费值 输入数据保证这个值小于231 样例输入 3129 样例输出 15 数据规模 对于30 的数据 保证有n 1000 对于50 的数据 保证有n 5000 对于全部的数据 保证有n 10000 显然 一个略强大的词 如果取每次最小的两堆合并 体力值一定最小当然要快排最小的两堆合并后 不一定最小 所以 总不能每次都快排吧 如果每次快排 效率 n n logn 五组当然 也可以再向后扫一遍 然后改变数组但如果有多个小的 显然 稍快但很容易错如果从大到小存 从后向前扫呢这样每次扫描都可以同时向前移位 同时由于已排过序 只要找到一个大于合并后果子数的就可以跳出 效率大大提高 一道坑爹的 Multiset 问题描述 Alice正在玩一个multiset 最初 集合中只有一个元素0 每一轮 集合中的每一个元素x都有3种可能的操作 1 x加上1 即x x 2 x分裂成两个非负整数y z 即x y z 且y 0 z 0 3 什么都不做 注意 在一轮中每个元素只能选择一种操作 Alice已经玩了很久了 但她并不知道自己已经玩了多少轮 现在给出最终的集合 请你输出Alice最少玩的轮数 输入格式 从文件multiset in中读入数据 第一行为一个整数 描述最终集合的大小 第二行为 个非负整数 为最终集合的每一个元素 输出格式 输出到文件multiset out中 输出唯一一行 Alice最少玩的轮数 样例输入 SampleInput110SampleInput241111SampleInput3503030 对于每个数 有0或非0两种情况对于0 每次操作中将0成对合并对于非0数 每次操作同时减一于是对于所有的数 按数值统计出现次数n减到0需要n次 减去之前的总次数 再算剩余多少0直到最大的数 再计算剩余的0计算剩余所有0合并需要的次数加上之前的次数 即为答案 可是可是 怎么确定怎么贪心呢 很大程度上 你不知道 然后就是拼人品当然 还是可以找找路子的 比如一些模板 堆问题最短路中的dijkstra和最小生成树prim活动安排之类 比如 可以改变一些条件 转化成一些不知道怎么形容的样子自己悟吧可以试一试 举反例 当然这要靠人品 所以请积德行善比如可以仔细观察条件 然后找到单个数据的变化过程 真的很玄乎 贪心法的求解过程用贪心法求解问题应该考虑如下几个方面 1 候选集合C 为了构造问题的解决方案 有一个候选集合C作为问题的可能解 即问题的最终解均取自于候选集合C 2 解集合S 随着贪心选择的进行 解集合S不断扩展 直到构成一个满足问题的完整解 3 解决函数solution 检查解集合S是否构成问题的完整解 4 选择函数select 即贪心策略 这是贪心法的关键 它指出哪个候选对象最有希望构成问题的解 选择函数通常和目标函数有关 5 可行函数feasible 检查解集合中加入一个候选对象是否可行 即解集合扩展后是否满足约束条件 例如 在付款问题中 可行函数是每一步选择的货币和已付出的货币相加不超过应付款 来自网上某大神的总结 贪心法的一般流程Greedy C C是问题的输入集合即候选集合 S 初始解集合为空集while notsolution S 集合S没有构成问题的一个解 x select C 在候选集合C中做贪心选择iffeasible S x 判断集合S中加入x后的解是否可行S S x C C x returnS 贪心法的基本要素对于一个具体的问题 怎么知道是否可用贪心算法解此问题 以及能否得到问题的最优解呢 这个问题很难给予肯定的回答 但是 从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质 贪心选择性质和最优子结构性质 子问题 假设为了解决某一优化问题 需要依次作出n个决策D1 D2 Dn 对于任何一个整数k 1 k n 以Dk作为问题的初始状态 来进行以后的决策 这样的问题就成为是原问题的一个子问题 1 贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择 换句话说 当考虑做何种选择的时候 我们只考虑对当前问题最佳的选择而不考虑子问题的结果 这是贪心算法可行的第一个基本要素 贪心算法以迭代的方式作出相继的贪心选择 每作一次贪心选择就将所求问题简化为规模更小的子问题 对于一个具体问题 要确定它是否具有贪心选择性质 必须证明每一步所作的贪心选择最终导致问题的整体最优解 2 最优子结构性质当一个问题的最优解包含其子问题的最优解时 称此问题具有最优子结构性质 问题的最优子结构性质是该问题可用贪心算法求解的关键特征 这样的问题 已知一些量将它们改变为一种固定的样子求最大最小值最优化问题能分成多个子问题的问题 很可能是贪心算法 应该可以发现这些题貌似都能