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

基于贪心的算法和应用1信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本贪心算法引入 【引例1】在n行m列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共n个数的和最大。 【分析】要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。2信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本贪心算法引入 【引例2】有1元、5元、10元、50元、100元、500元的硬币各C1、C5、C10、C50、C100、C500枚。现在要用这些硬币来支付A元，最少需要多少枚硬币？ 【分析】优先使用面值大的硬币。3信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本贪心算法定义

贪心算法是从问题的某一个初始状态出发，通过逐步构造最优解的方法向给定的目标前进，并期望通过这种方法产生出一个全局最优解的方法。

小球表示当前状态,

红箭头表示当前最优决策；

蓝箭头表示其他决策。

方向4信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本贪心算法的特点

贪心标准选择：所谓贪心标准选择就是应用当前“最好”的标准作为统一标准，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前看似最佳的选择。

最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。5信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本贪心算法的特点 【引例3】部分背包问题

有一个背包，容量是M＝150，有7个物品，物品可以分割成任意大小，要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品ABCDEFG体积35306050401025价值104030503540306信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本贪心算法的特点 【分析】

有以下几种策略可供选择： （1）每次挑选价值最大的物品装入背包，得到的结果是否最优？ （2）每次挑选所占空间最小的物品装入是否能得到最优解？ （3）每次选取单位容量价值最大的物品。7信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本贪心算法的特点

解题一般步骤: 1、设计数据找规律；

2、进行贪心猜想；

3、正确性证明（严格证明和一般证明） ★一般证明：列举反例； ★严格证明：数学归纳和反证法；

4、程序实现。8信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题※删数问题（NOI1995）※取数问题（IOI1996）※接水问题※最大整数※均分纸牌（NOIP2002）※三国游戏（NOIP2010）※火柴排队（NOIP2013）9信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题 【例1】删数问题（NOI1994） 键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。 输出剩下的最小数。10信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题 【分析】

因为要删除S个数字，可以一个一个地删，每一次删除的目的都是使剩下的数尽量小。 那么在每一次删除时，应该选择哪个数字呢？最大的那个数字？还是最左边的那个数字？例如5768，删除7可以使剩余的数最小。//删除7会使后面的较小数前移，从而得到更小的数。如果不删除7，删除之前的较小数，会使大数7前移。删除7之后的较小数，则比删除7这个较大数得到的数要大。11信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题

结论： 每一次删除的数字应该是这个数字序列中最左边递减序列的第一个数字。具体操作为，按高位到低位的方向搜索递减区间。若不存在递减区间，则删除尾数字，否则删除递减区间的首数符，这样就形成一个最小的数。 重复上述规则，直到删除S个数字为止。12信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题

例如：N＝8796542，S＝4

第一次：N＝8796542，删除8； 第二次：N＝796542，删除9； 第三次：N＝76542，删除7； 第四次：N＝6542，删除6，得到542。13信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题

readln(n); readln(s); fork:=1tosdo begin i:=1; while(i<length(n))and(n[i]<=n[i+1])do inc(i); delete(n,i,1); end;

while(length(n)>1)and(n[1]=‘0’)dodelete(n,1,1) writeln(n);14信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本讨论一 【例2】取数问题（IOI1996） 给出2n（n≤100）个自然数（小于等于30000），将这2n个自然数排成一列，游戏双方A和B从中轮流取数，只允许从两端取数，A方先取，然后B方再取。取完时，谁取的数字总和最大为取胜方；若双方和相等，则B胜，试问A方是否有必胜策略？15信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本讨论一

输入格式：两行，第一行一个整数n，第二行有2n个自然数。 输出格式：只有一行，若A有必胜策略，则输出“YES”，否则输出“NO”。 输入样例：

4 79364253

输出样例：

YES16信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本讨论一 【分析】

若采用这样一种策略，让A方每次取数列两端较大的那个数，则B方也会这样取，对于样例：79364253，

A方会取得7、3、4、5，

B方会取得9、6、2、3，

A方的总和为19，B方的总和为20，按照规则，输出“NO”。17信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本讨论一 【分析】

如果A方取走奇数位置上的数后，剩下的两端都是偶数位置上的数，如果A方取走偶数位置上的数后，剩下的两端都是奇数位置上的数。

A方既可以取走所有奇数位置上的数，或者取走所有偶数位置上的数。 另一个策略：让A方取“数和较大的奇（或偶）位置上的所有数”。18信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本讨论一

readln(n); fori:=1to2*ndo read(a[i]); sa:=0; sb:=0; fori:=1tondo begin sa:=sa+a[2*i-1]; sb:=sb+a[2*i]; end; ifsa=sb thenwriteln(‘NO’) elsewriteln(‘YES’);19信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题 【例3】排队接水 有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得这n个人平均等待时间最小。 输入样例：

10 56121991000234335599812

输出样例：

291.9020信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题 【分析】

平均等待时间就是每个人的等待时间之和再除以n，因为n是常数，所以等待时间之和最小也就等同于平均等待时间最小。 Total=Ti1+(Ti1+Ti2)+(Ti1+Ti2+Ti3)+…(Ti1+Ti2+…+Tin) =nTi1+(n-1)Ti2+(n-2)Ti3+…+Tin

如果让Ti1最小，Ti2次小，…，Tin最大，也就是把接水时间少的人尽可能排在前面，总的等待时间就最少了。21信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题 【例4】最大整数 设有n个正整数(n<=20,Longint范围内),将它们联接成一排组成一个最大的多位整数。 例如:n=3时,3个整数13,312,343联接成的最大整数为:34331213。 又如:n=4时,4个整数7,13,4,246联接成的最大整数为:7424613。 程序输入:n及n个数。 程序输出:联接成的多位数。22信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题 【分析】

本例因为涉及将两个自然数连接起来的问题，采用字符串来处理比较方便。首先我们自然会想到大的字符串应该排在前面，因为如果A与B是两个由数字字符构成的字符串且A>B，一般情况下有A+B>B+A，但是当A=B+C时，按字符串的大小定义有A>B，但有可能会出现A+B<B+A的情况，如A=121,B=12,则A+B=12112,B+A=12121,A+B<B+A。23信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题【分析】

根据题意用另一种字符串比较办法，将A+B与B+A相比较，如果前者大于后者，则认为A>B，按这一定义将所有的数字字符串从大到小排序后连接起来所得到的数字字符串即是问题的解。排序时先将所有字符串中的最大值选出来存在数组的第一个元素中，再从第二至最后一个元素中最大的字符串选出来存在数组的第二个元素中，直到从最后两个元素中选出最大的字符串存在数组的倒数第二个元素中为止。24信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题

fori:=1ton-1doforj:=i+1tondoifnum[i]+num[j]<num[j]+num[i]thenbegintemp:=num[i];num[i]:=num[j];num[j]:=tempend; fori:=1tondo write(num[i]); writeln;25信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题 【例5】均分纸牌（NOIP2002） 有N堆纸牌，编号分别为1，2，……，N。第i堆有a[i]张纸牌（a[i]≤10000）,但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N－1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆牌数都一样多。26信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题

例如：N＝4，纸牌数分别为9、8、17、6，移动3次可达到目的。 第一次：从第3堆取4张牌放到第4堆；

9、8、13、10

第二次：从第3堆取3张牌放到第2堆；

9、11、10、10

第三次：从第2堆取1张牌放到第1堆。

10、10、10、1027信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题 【分析】

设v为均分后每堆纸牌的张数，s为最少移动次数。按照从左到右的顺序移动纸牌。如果第i堆的纸牌数a[i]不等于v，则移动一次，分两种情况移动： （1）如果a[i]>v，则将a[i]-v张纸牌从第i堆移动到第i+1堆； （2）如果a[i]<v，则将v-a[i]张纸牌从第i+1堆移动第i堆。28信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题 【分析】

从第i+1堆中取出纸牌给第i堆的过程中，可能会出现第i+1堆的纸牌数小于0的情况。如n＝3，三堆纸牌数为1、2、27，v＝10，要从第2堆移动9张纸牌到第1堆，而第2堆只有2张纸牌可以移动。按照规则会得到10、-7、27，再从第3堆移动17张纸牌到第2堆，即得到10、10、10。在移动过程中，只要改变一下移动的顺序，而移动的次数不会变。29信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本经典例题 readln(n); v:=0; fori:=1tondo begin read(a[i]); v:=v+a[i]; end; v:=vdivn;s:=0; fori:=1ton-1do ifa[i]<>v//如果之前的调整使得值正好为v，不用移动 thenbegin inc(s);a[i+1]:=a[i+1]+a[i]-v; end; writeln(s);30信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本讨论二【例6】三国游戏（NOIP2010普及组第4题）

小涵很喜欢电脑游戏，这些天他正在玩一个叫做《三国》的游戏。

在游戏中，小涵和计算机各执一方，组建各自的军队进行对战。游戏中共有N位武将（N为偶数且不小于4），任意两个武将之间有一个“默契值”，表示若此两位武将作为一对组合作战时，该组合的威力有多大。游戏开始前，所有武将都是自由的（称为自由武将，一旦某个自由武将被选中作为某方军队的一员，那么他就不再是自由31信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本讨论二

武将了），换句话说，所谓的自由武将不属于任何一方。游戏开始，小涵和计算机要从自由武将中挑选武将组成自己的军队，规则如下：小涵先从自由武将中选出一个加入自己的军队，然后计算机也从自由武将中选出一个加入计算机方的军队。接下来一直按照“小涵→计算机→小涵→……”的顺序选择武将，直到所有的武将被双方均分完。然后，程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武，拥有更高默契值的一对武将组合获胜，表示两军交战，拥有获胜武将组合的一方获胜。32信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本讨论二

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

下面举例说明计算机的选将策略，例如，游戏中一共有6个武将，他们相互之间的默契值如下表所示33信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本讨论二

双方选将过程如下所示：双方选将过程如下所示：武将相互之间的默契值：34信息学奥赛NOIP教程基于贪心的算法和应用5/8/2024点击添加文本点击添加文本点击添加文本点击添加文本讨论二

小涵想知道，如果计算机在一局游戏中始终坚持上面这个策略，那么自己有没有可能必胜？如果有，在所有可能的胜利结局中，自己那对用于比武的武将组合的默契值最大是多少？