信息学奥赛NOIP教程基于贪心的算法和应用课件

《信息学奥赛NOIP教程基于贪心的算法和应用课件》由会员分享，可在线阅读，更多相关《信息学奥赛NOIP教程基于贪心的算法和应用课件（38页珍藏版）》请在装配图网上搜索。

1、基于贪心的算法和应用1贪贪心心算算法法引引入入【引例引例1 1】在在n n行行m m列的正整数矩阵中，要求列的正整数矩阵中，要求从每行中选出从每行中选出1 1个数，使得选出的总共个数，使得选出的总共n n个个数的和最大。数的和最大。【分析分析】要使总和最大，则每个数要尽可要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。能大，自然应该选每行中最大的那个数。2贪贪心心算算法法引引入入【引例引例2 2】有有1 1元、元、5 5元、元、1010元、元、5050元、元、100100元、元、500500元的硬币各元的硬币各C1C1、C5C5、C10C10、C50C50、C100C100、C

2、500C500枚。现在要用这些硬币来支付枚。现在要用这些硬币来支付A A元，最少需要多少枚硬币？元，最少需要多少枚硬币？【分析分析】优先使用面值大的硬币。优先使用面值大的硬币。3贪贪心心算算法法定定义义 贪心算法是从问题的某一个初始状态贪心算法是从问题的某一个初始状态出发，通过逐步构造最优解的方法向给定出发，通过逐步构造最优解的方法向给定的目标前进，并期望通过这种方法产生出的目标前进，并期望通过这种方法产生出一个全局最优解的方法。一个全局最优解的方法。小球表示当前状态小球表示当前状态,红箭头表示当前最优决策；红箭头表示当前最优决策；蓝箭头表示其他决策。蓝箭头表示其他决策。方向方向4贪贪心心算算

3、法法的的特特点点 贪心标准选择：所谓贪心标准选择就是应贪心标准选择：所谓贪心标准选择就是应用当前用当前“最好最好”的标准作为统一标准，将原问的标准作为统一标准，将原问题变为一个相似的但规模更小的子问题，而后题变为一个相似的但规模更小的子问题，而后的每一步都是当前看似最佳的选择。的每一步都是当前看似最佳的选择。最优子结构：当一个问题的最优解包含其最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构子问题的最优解时，称此问题具有最优子结构性质。性质。5贪贪心心算算法法的的特特点点【引例引例3 3】部分背包问题部分背包问题 有一个背包，容量是有一个背包，容量是M M15015

4、0，有，有7 7个物个物品，物品可以分割成任意大小，要求尽可品，物品可以分割成任意大小，要求尽可能让装入背包中的物品总价值最大，但不能让装入背包中的物品总价值最大，但不能超过总容量。能超过总容量。6贪贪心心算算法法的的特特点点【分析分析】有以下几种策略可供选择：有以下几种策略可供选择：（1 1）每次挑选价值最大的物品装入背包，）每次挑选价值最大的物品装入背包，得到的结果是否最优？得到的结果是否最优？（2 2）每次挑选所占空间最小的物品装入是）每次挑选所占空间最小的物品装入是否能得到最优解？否能得到最优解？（3 3）每次选取单位容量价值最大的物品。）每次选取单位容量价值最大的物品。7贪贪心心算算

5、法法的的特特点点解题一般步骤解题一般步骤:1 1、设计数据找规律；、设计数据找规律；2 2、进行贪心猜想；、进行贪心猜想；3 3、正确性证明（严格证明和一般证明）、正确性证明（严格证明和一般证明）一般证明：列举反例；一般证明：列举反例；严格证明：数学归纳和反证法；严格证明：数学归纳和反证法；4 4、程序实现。、程序实现。8经经典典例例题题 删数问题（删数问题（NOI 1995NOI 1995）取数问题（取数问题（IOI 1996IOI 1996）接水问题接水问题 最大整数最大整数 均分纸牌（均分纸牌（NOIP 2002NOIP 2002）三国游戏（三国游戏（NOIP 2010NOIP 2010

6、）火柴排队（火柴排队（NOIP 2013NOIP 2013）9经经典典例例题题【例例1 1】删数问题（删数问题（NOI 1994NOI 1994）键盘输入一个高精度的正整数键盘输入一个高精度的正整数N N，去掉，去掉其中任意其中任意S S个数字后剩下的数字按原左右次个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的序将组成一个新的正整数。编程对给定的N N和和S S，寻找一种方案使得剩下的数字组成的，寻找一种方案使得剩下的数字组成的新数最小。新数最小。输出剩下的最小数。输出剩下的最小数。10经经典典例例题题【分析分析】因为要删除因为要删除S S个数字，可以一个一个地删，个数字，可

7、以一个一个地删，每一次删除的目的都是使剩下的数尽量小。每一次删除的目的都是使剩下的数尽量小。那么在每一次删除时，应该选择哪个数那么在每一次删除时，应该选择哪个数字呢？最大的那个数字？还是最左边的那个字呢？最大的那个数字？还是最左边的那个数字？数字？例如例如57685768，删除，删除7 7可以使剩余的数最小。可以使剩余的数最小。/删除删除7 7会使后面的较小数前移，从而得到更小的数。如果不删除会使后面的较小数前移，从而得到更小的数。如果不删除7 7，删除之前的较小数，会使，删除之前的较小数，会使大数大数7 7前移。删除前移。删除7 7之后的较小数，则比删除之后的较小数，则比删除7 7这个较大数

8、得到的数要大。这个较大数得到的数要大。11经经典典例例题题结论：结论：每一次删除的数字应该是这个数字序列每一次删除的数字应该是这个数字序列中最左边递减序列的第一个数字。具体操作中最左边递减序列的第一个数字。具体操作为，按高位到低位的方向搜索递减区间。若为，按高位到低位的方向搜索递减区间。若不存在递减区间，则删除尾数字，否则删除不存在递减区间，则删除尾数字，否则删除递减区间的首数符，这样就形成一个最小的递减区间的首数符，这样就形成一个最小的数。数。重复上述规则，直到删除重复上述规则，直到删除S S个数字为止。个数字为止。12经经典典例例题题例如：例如：N N，S S4 4第一次：第一次：N N，

9、删除，删除8 8；第二次：第二次：N N796542796542，删除，删除9 9；第三次：第三次：N N7654276542，删除，删除7 7；第四次：第四次：N N65426542，删除，删除6 6，得到，得到542542。13经经典典例例题题readln(n);readln(n);readln(s);readln(s);for k:=1 to s dofor k:=1 to s dobeginbegin i:=1;i:=1;while(ilength(n)and(ni=ni+1)do while(ilength(n)and(ni1)and(n1=0)dowhile(length(n)1)

10、and(n1=0)do delete(n,1,1)delete(n,1,1)writeln(n);writeln(n);14讨讨论论一一【例例2 2】取数问题（取数问题（IOI 1996IOI 1996）给出给出2n2n（n100n100）个自然数（小于等）个自然数（小于等于于3000030000），将这），将这2n2n个自然数排成一列，游个自然数排成一列，游戏双方戏双方A A和和B B从中轮流取数，只允许从两端从中轮流取数，只允许从两端取数，取数，A A方先取，然后方先取，然后B B方再取。取完时，方再取。取完时，谁取的数字总和最大为取胜方；若双方和谁取的数字总和最大为取胜方；若双方和相等，

11、则相等，则B B胜，试问胜，试问A A方是否有必胜策略？方是否有必胜策略？15讨讨论论一一输入格式：两行，第一行一个整数输入格式：两行，第一行一个整数n n，第二，第二行有行有2n2n个自然数。个自然数。输出格式：只有一行，若输出格式：只有一行，若A A有必胜策略，则有必胜策略，则输出输出“YES”YES”，否则输出，否则输出“NO”NO”。输入样例：输入样例：4 47 9 3 6 4 2 5 37 9 3 6 4 2 5 3输出样例：输出样例：YESYES16讨讨论论一一【分析分析】若采用这样一种策略，让若采用这样一种策略，让A A方每次取数方每次取数列两端较大的那个数，则列两端较大的那个数

12、，则B B方也会这样取，方也会这样取，对于样例：对于样例：7 9 3 6 4 2 5 37 9 3 6 4 2 5 3，A A方会取得方会取得7 7、3 3、4 4、5 5，B B方会取得方会取得9 9、6 6、2 2、3 3，A A方的总和为方的总和为1919，B B方的总和为方的总和为2020，按，按照规则，输出照规则，输出“NO”NO”。17讨讨论论一一【分析分析】如果如果A A方取走奇数位置上的数后，剩下的方取走奇数位置上的数后，剩下的两端都是偶数位置上的数，如果两端都是偶数位置上的数，如果A A方取走偶方取走偶数位置上的数后，剩下的两端都是奇数位数位置上的数后，剩下的两端都是奇数位置

13、上的数。置上的数。A A方既可以取走所有奇数位置上的数，或方既可以取走所有奇数位置上的数，或者取走所有偶数位置上的数。者取走所有偶数位置上的数。另一个策略：让另一个策略：让A A方取方取“数和较大的奇数和较大的奇（或偶）位置上的所有数（或偶）位置上的所有数”。18讨讨论论一一readln(n);readln(n);for i:=1 to 2*n dofor i:=1 to 2*n do read(ai);read(ai);sa:=0;sa:=0;sb:=0;sb:=0;for i:=1 to n dofor i:=1 to n dobeginbegin sa:=sa+a2*i-1;sa:=sa

14、+a2*i-1;sb:=sb+a2*i;sb:=sb+a2*i;end;end;if sa=sbif sa=sbthen writeln(NO)then writeln(NO)else writeln(YES);else writeln(YES);19经经典典例例题题【例例3 3】排队接水排队接水 有有n n个人在一个水龙头前排队接水，假如每个个人在一个水龙头前排队接水，假如每个人接水的时间为人接水的时间为TiTi，请编程找出这，请编程找出这n n个人排队的一个人排队的一种顺序，使得这种顺序，使得这n n个人平均等待时间最小。个人平均等待时间最小。输入样例：输入样例：101056 12 1 9

15、9 1000 234 33 55 99 81256 12 1 99 1000 234 33 55 99 812输出样例：输出样例：291.90291.9020经经典典例例题题【分析分析】平平均均等等待待时时间间就就是是每每个个人人的的等等待待时时间间之之和和再再除除以以n n，因因为为n n是是常常数数，所所以以等等待待时时间间之之和和最最小小也也就就等等同同于于平均等待时间最小。平均等待时间最小。Total=TTotal=Ti1i1+(T+(Ti1i1+T+Ti2i2)+(T)+(Ti1i1+T+Ti2i2+T+Ti3i3)+(T)+(Ti1i1+T+Ti2i2+T+Tinin)=nT =n

16、Ti1i1+(n-1)T+(n-1)Ti2i2+(n-2)T+(n-2)Ti3i3+T+Tinin 如如果果让让T Ti1i1最最小小，T Ti2i2次次小小，T Tinin最最大大，也也就就是是把把接接水水时时间间少少的的人人尽尽可可能能排排在在前前面面，总总的的等等待待时时间间就就最少了。最少了。21经经典典例例题题【例例4 4】最大整数最大整数 设有设有n n个正整数个正整数(n=20,Longint(nBAB，一般情况下有一般情况下有A+BB+AA+BB+A，但是当，但是当A=B+CA=B+C时，按字时，按字符串的大小定义有符串的大小定义有ABAB，但有可能会出现，但有可能会出现A+B

17、B+AA+BB+A的情况，如的情况，如A=121,B=12,A=121,B=12,则则A+B=12112,B+A=12121,A+BB+AA+B=12112,B+A=12121,A+BBAB，按，按这一定义将所有的数字字符串从大到小排序后连这一定义将所有的数字字符串从大到小排序后连接起来所得到的数字字符串即是问题的解。排序接起来所得到的数字字符串即是问题的解。排序时先将所有字符串中的最大值选出来存在数组的时先将所有字符串中的最大值选出来存在数组的第一个元素中，再从第二至最后一个元素中最大第一个元素中，再从第二至最后一个元素中最大的字符串选出来存在数组的第二个元素中，直到的字符串选出来存在数组的

18、第二个元素中，直到从最后两个元素中选出最大的字符串存在数组的从最后两个元素中选出最大的字符串存在数组的倒数第二个元素中为止。倒数第二个元素中为止。24经经典典例例题题for i:=1 to n-1 dofor i:=1 to n-1 do for j:=i+1 to n do for j:=i+1 to n do if numi+numjnumj+numi if numi+numjvaiv，则将，则将ai-vai-v张纸牌从第张纸牌从第i i堆堆移动到第移动到第i+1i+1堆；堆；（2 2）如果）如果aivaiv，则将，则将v-aiv-ai张纸牌从第张纸牌从第i+1i+1堆移动第堆移动第i i

19、堆。堆。28经经典典例例题题【分析分析】从第从第i+1i+1堆中取出纸牌给第堆中取出纸牌给第i i堆的过程中，可能堆的过程中，可能会出现第会出现第i+1i+1堆的纸牌数小于堆的纸牌数小于0 0的情况。如的情况。如n n3 3，三堆纸牌数为三堆纸牌数为1 1、2 2、2727，v v1010，要从第，要从第2 2堆移动堆移动9 9张纸牌到第张纸牌到第1 1堆，而第堆，而第2 2堆只有堆只有2 2张纸牌可以移动。张纸牌可以移动。按照规则会得到按照规则会得到1010、-7-7、2727，再从第，再从第3 3堆移动堆移动1717张张纸牌到第纸牌到第2 2堆，即得到堆，即得到1010、1010、1010

20、。在移动过程中，。在移动过程中，只要改变一下移动的顺序，而移动的次数不会变。只要改变一下移动的顺序，而移动的次数不会变。29经经典典例例题题readln(n);readln(n);v:=0;v:=0;for i:=1 to n dofor i:=1 to n dobeginbegin read(ai);read(ai);v:=v+ai;v:=v+ai;end;end;v:=v div n;s:=0;v:=v div n;s:=0;for i:=1 to n-1 dofor i:=1 to n-1 do if aiv if aiv /如果之前的调整使得值正好为如果之前的调整使得值正好为v v，不

21、用移动，不用移动 then begin then begin inc(s);ai+1:=ai+1+ai-v;inc(s);ai+1:=ai+1+ai-v;end;end;writeln(s);writeln(s);30讨讨论论二二【例例6 6】三国游戏（三国游戏（NOIP2010NOIP2010普及组第普及组第4 4题）题）小涵很喜欢电脑游戏，这些天他正在玩一个小涵很喜欢电脑游戏，这些天他正在玩一个叫做叫做三国三国的游戏。的游戏。在游戏中，小涵和计算机各执一方，组建各在游戏中，小涵和计算机各执一方，组建各自的军队进行对战。游戏中共有自的军队进行对战。游戏中共有N N位武将（位武将（N N为偶为

22、偶数且不小于数且不小于4 4），任意两个武将之间有一个），任意两个武将之间有一个“默契默契值值”，表示若此两位武将作为一对组合作战时，表示若此两位武将作为一对组合作战时，该组合的威力有多大。游戏开始前，所有武将都该组合的威力有多大。游戏开始前，所有武将都是自由的（称为自由武将，一旦某个自由武将被是自由的（称为自由武将，一旦某个自由武将被选中作为某方军队的一员，那么他就不再是自由选中作为某方军队的一员，那么他就不再是自由31讨讨论论二二武将了），换句话说，所谓的自由武将不属于任武将了），换句话说，所谓的自由武将不属于任何一方。游戏开始，小涵和计算机要从自由武将何一方。游戏开始，小涵和计算机要从自

23、由武将中挑选武将组成自己的军队，规则如下：小涵先中挑选武将组成自己的军队，规则如下：小涵先从自由武将中选出一个加入自己的军队，然后计从自由武将中选出一个加入自己的军队，然后计算机也从自由武将中选出一个加入计算机方的军算机也从自由武将中选出一个加入计算机方的军队。接下来一直按照队。接下来一直按照“小涵小涵计算机计算机小涵小涵”的顺序选择武将，直到所有的武将被双的顺序选择武将，直到所有的武将被双方均分完。然后，程序自动从双方军队中各挑出方均分完。然后，程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行一对默契值最高的武将组合代表自己的军队进行二对二比武，拥有更高默契值的一对武将组

24、合获二对二比武，拥有更高默契值的一对武将组合获胜，表示两军交战，拥有获胜武将组合的一方获胜，表示两军交战，拥有获胜武将组合的一方获胜。胜。32讨讨论论二二 已知计算机一方选择武将的原则是尽量破坏已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合，它采取的具体策对手下一步将形成的最强组合，它采取的具体策略如下：任何时刻，轮到计算机挑选时，它会尝略如下：任何时刻，轮到计算机挑选时，它会尝试将对手军队中的每个武将与当前每个自由武将试将对手军队中的每个武将与当前每个自由武将进行一一配对，找出所有配对中默契值最高的那进行一一配对，找出所有配对中默契值最高的那对武将组合，并将该组合中的自由武

25、将选入自己对武将组合，并将该组合中的自由武将选入自己的军队。的军队。下面举例说明计算机的选将策略，例如，游下面举例说明计算机的选将策略，例如，游戏中一共有戏中一共有 6 6个武将，他们相互之间的默契值如个武将，他们相互之间的默契值如下表所示下表所示33讨讨论论二二双方选将过程如下所示：双方选将过程如下所示：双方选将过程如下所示：双方选将过程如下所示：武将相互之间的默契值武将相互之间的默契值：34讨讨论论二二 小涵想知道，如果计算机在一局游戏中始终小涵想知道，如果计算机在一局游戏中始终坚持上面这个策略，那么自己有没有可能必胜？坚持上面这个策略，那么自己有没有可能必胜？如果有，在所有可能的胜利结局中，自己那对用如果有，在所有可能的胜利结局中，自己那对用于比武的武将组合的默契值最大是多少？于比武的武将组合的默契值最大是多少？假设整个游戏过程中，对战双方任何时候均假设整个游戏过程中，对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。能看到自由武将队中的武将和对方军队的武将。为了简化问题，保证对于不同的武将组合，其默为了简化问题，保证对于不同的武将组合，其默契值均不相同。契值均不相同。35讨讨论论二二【分析分析】165432333236讨讨论论二二【分析分析】1876543237讨讨论论二二【分析分析】1876543238