NOIP中的贪心

1、NOIP中的贪心Greedy Algorithm贪一贪就有分了哈哈哈定义 将整个问题分成若干个子问题 通过每个子问题的最优解求出整个问题的最优解是不是so easy 就像在n*m的矩阵中，每行取一个数，使它们的和最大 不用说你也知道怎么做 但是. 你觉得考试有那么裸么？ 开玩笑！注意 当且仅当每个当前最优解的选择能导出总体最优解，才能用贪心 当然，你必须选对拿什么贪，或者说，什么策略 搞得像犯罪一样.能贪么？ 比如0-1背包，肯定不能按单位体积价值去贪心 但是部分背包可以 我相信你能分清它们 如果你分不清，RMB会告诉你NOIP2002均分纸牌均分纸牌问题描述有 N 堆纸牌，编号分别为 1，2

2、，, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为：98176移动3次可达到目的：从 取 4 张牌放到 （9 8 13 10） - 从 取 3 张牌放到 （9 11 10 10）- 从 取 1 张牌放到（10 10 10 10）。输 入：键盘输入文件名。文件格式：N（N 堆纸牌，1

3、 = N = 100）A1 A2 An （N 堆纸牌，每堆纸牌初始数，l= Ai =10000）输 出：输出所有堆均达到相等时的最少移动次数。 是不是想大吼一句：“这是贪心？” 没错这就是，好好想想吧 接下来我要第一次试用ppt的SmartArt功能 你们先想着1.试题几乎不可能是裸的所以要改一改2.只要把每堆的数减去平均数，各堆的正负就会不同把所有堆都变成0的次数，就是答案3.然后从左往右遍历，把每堆的数移到后一堆即可注意如果出现0，要跳过不管，否则会多算NOIP1999拦截导弹某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意

4、的高度，但是以后每一发炮弹都不能 高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 样例：INPUT 389 207 155 300 299 170 158 65 OUTPUT 6（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数） 话说这是我们的第一道贪心题 当时直接理解错题意 然后呵呵 所以如果理解对的话，很容易能想到贪心 对于每套系统，只需存它拦截的最

5、后一枚导弹的高度 如果新的导弹比所有系统能拦截的高度都高，那就再来一套 否则选择能拦截该导弹的高度最低的系统 代码很容易，不再cv 当然，此题也可以动规解决，那就不是我的事情了NOIP2004 合并果子 【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多 多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗 的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每

6、个果子重量都为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种果子的数目。【输出文件】

7、输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。【样例输入】31 2 9【样例输出】15【数据规模】对于30%的数据，保证有n = 1000；对于50%的数据，保证有n = 5000；对于全部的数据，保证有n =0, z = 0。 3、什么都不做。 注意，在一轮中每个元素只能选择一种操作。 Alice 已经玩了很久了， 但她并不知道自己已经玩了多少轮。 现在给出最终的集合，请你输出 Alice 最少玩的轮数。 【输入格式】 从文件 multiset.in 中读入数据。第一行为一个整数，描述最终集合的大小。第二行为个非负整数，为最终

8、集合的每一个元素。 【输出格式】 输出到文件 multiset.out 中。 输出唯一一行，Alice 最少玩的轮数。 【样例输入】 Sample Input 1 1 0 Sample Input 2 4 1 1 1 1 Sample Input 3 5 0 3 0 3 0 对于每个数，有0或非0两种情况 对于0，每次操作中将0成对合并 对于非0数，每次操作同时减一 于是对于所有的数，按数值统计出现次数 n减到0需要n次，减去之前的总次数，再算剩余多少0 直到最大的数，再计算剩余的0 计算剩余所有0合并需要的次数 加上之前的次数，即为答案可是可是，怎么确定怎么贪心呢 很大程度上，你不知道，然后

9、就是拼人品 当然，还是可以找找路子的比如一些模板 堆问题 最短路中的dijkstra和最小生成树prim 活动安排之类比如 可以改变一些条件，转化成一些不知道怎么形容的样子 自己悟吧 可以试一试，举反例，当然这要靠人品，所以请积德行善 比如可以仔细观察条件，然后找到单个数据的变化过程 。 真的很玄乎 贪心法的求解过程贪心法的求解过程 用贪心法求解问题应该考虑如下几个方面： （1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。 （2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。 （3）解决函数soluti

10、on：检查解集合S是否构成问题的完整解。 （4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。 （5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。 贪心法的一般流程贪心法的一般流程 Greedy(C) /C是问题的输入集合即候选集合 S= ; /初始解集合为空集 while (not solution(S) /集合S没有构成问题的一个解 x=select(C); /在候选集合C中做贪心选择 i

11、f feasible(S, x) /判断集合S中加入x后的解是否可行 S=S+x; C=C-x; return S; 贪心法的基本要素 对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。 但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。 子问题：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，Dn，对于任何一个整数k，1kn，以Dk作为问题的初始状态，来进行以后的决策，这样的问题就成为是原问题的一个子问题。 1.贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以

12、通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。 贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2.最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。这样的问题 已知一些量将它们改变为一种固定的样子 求最大最小值 最优化问题 能分成多个子问题的问题 .很可能是贪心算法 应该可以发现这些题貌似都能动规解决 当然它们