day9基于贪心的算法和应用举例-杨志军

基于贪心的算法和应用举例2014年7月赣榆高级中学贪心算法引入

【引例1】在n行m列的正整数矩阵中，要求从每行中选出1个数，使得选出的总共n个数的和最大。 【分析】要使总和最大，则每个数要尽可能大，自然应该选每行中最大的那个数。贪心算法引入

【引例2】有1元、5元、10元、50元、100元、500元的硬币各C1、C5、C10、C50、C100、C500枚。现在要用这些硬币来支付A元，最少需要多少枚硬币？ 【分析】优先使用面值大的硬币。贪心算法定义

贪心算法是从问题的某一个初始状态出发，通过逐步构造最优解的方法向给定的目标前进，并期望通过这种方法产生出一个全局最优解的方法。方向红箭头表示当前最优决策；蓝箭头表示其他决策；小球表示当前状态。贪心算法的特点

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

最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。贪心算法的特点

【引例3】部分背包问题

有一个背包，容量是M＝150，有7个物品，物品可以分割成任意大小，要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品ABCDEFG体积35306050401025价值10403050354030贪心算法的特点

【分析】

有以下几种策略可供选择：

（1）每次挑选价值最大的物品装入背包，得到的结果是否最优？

（2）每次挑选所占空间最小的物品装入是否能得到最优解？

（3）每次选取单位容量价值最大的物品。贪心算法的特点

解题一般步骤: 1、设计数据找规律； 2、进行贪心猜想； 3、正确性证明（严格证明和一般证明） ★一般证明：列举反例； ★严格证明：数学归纳和反证法； 4、程序实现。经典例题※删数问题（NOI1995）※取数问题（IOI1996）※接水问题※最大整数※均分纸牌（NOIP2002）※合并果子（NOIP2004）※三国游戏（NOIP2010）※火柴排队（NOIP2013）※货车运输（NOIP2013）【例1】删数问题（NOI1994）

键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。

输出剩下的最小数。经典例题经典例题

【分析】

因为要删除S个数字，可以一个一个地删，每一次删除的目的都是使剩下的数尽量小。

那么在每一次删除时，应该选择哪个数字呢？最大的那个数字？还是最左边的那个数字？

例如5768，删除7可以使剩余的数最小。经典例题

结论：

每一次删除的数字应该是这个数字序列中最左边递减序列的第一个数字。具体操作为，按高位到低位的方向搜索递减区间。若不存在递减区间，则删除尾数字，否则删除递减区间的首数符，这样就形成一个最小的数。

重复上述规则，直到删除S个数字为止。经典例题

例如：N＝8796542，S＝4

第一次：N＝8796542，删除8；

第二次：N＝796542，删除9；

第三次：N＝76542，删除7；

第四次：N＝6542，删除6，得到542。经典例题

参考程序 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);讨论一

【例2】取数问题（IOI1996）

给出2n（n≤100）个自然数（小于等于30000），将这2n个自然数排成一列，游戏双方A和B从中轮流取数，只允许从两端取数，A方先取，然后B方再取。取完时，谁取的数字总和最大为取胜方；若双方和相等，则B胜，试问A方是否有必胜策略？讨论一

输入格式：两行，第一行一个整数n，第二行有2n个自然数。

输出格式：只有一行，若A有必胜策略，则输出“YES”，否则输出“NO”。

输入样例： 4 79364253

输出样例： YES讨论一 【分析】

若采用这样一种策略，让A方每次取数列两端较大的那个数，则B方也会这样取，对于样例：79364253， A方会取得7、3、4、5， B方会取得9、6、2、3， A方的总和为19，B方的总和为20，按照规则，输出“NO”。讨论一

【分析】

如果A方取走奇数位置上的数后，剩下的两端都是偶数位置上的数，如果A方取走偶数位置上的数后，剩下的两端都是奇数位置上的数。 A方既可以取走所有奇数位置上的数，或者取走所有偶数位置上的数。

另一个策略：让A方取“数和较大的奇（或偶）位置上的所有数”。讨论一

参考程序 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’);经典例题 【例3】排队接水

有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得这n个人平均等待时间最小。

输入样例： 10 56121991000234335599812

输出样例： 291.90经典例题

【分析】

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

如果让Ti1最小，Ti2次小，…，Tin最大，也就是把接水时间少的人尽可能排在前面，总的等待时间就最少了。经典例题【例4】最大整数

设有n个正整数(n<=20,Longint范围内),将它们联接成一排组成一个最大的多位整数。

例如:n=3时,3个整数13,312,343联接成的最大整数为:34331213。

又如:n=4时,4个整数7,13,4,246联接成的最大整数为:7424613。

程序输入:n及n个数。

程序输出:联接成的多位数。经典例题 【分析】

本例因为涉及将两个自然数连接起来的问题，采用字符串来处理比较方便。首先我们自然会想到大的字符串应该排在前面，因为如果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。经典例题 【分析】

根据题意用另一种字符串比较办法，将A+B与B+A相比较，如果前者大于后者，则认为A>B，按这一定义将所有的数字字符串从大到小排序后连接起来所得到的数字字符串即是问题的解。排序时先将所有字符串中的最大值选出来存在数组的第一个元素中，再从第二至最后一个元素中最大的字符串选出来存在数组的第二个元素中，直到从最后两个元素中选出最大的字符串存在数组的倒数第二个元素中为止。经典例题

参考程序 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;经典例题

【例5】均分纸牌（NOIP2002）

有N堆纸牌，编号分别为1，2，……，N。第i堆有a[i]张纸牌（a[i]≤10000）,但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N－1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆牌数都一样多。经典例题

例如：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、10经典例题 【分析】

设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堆。经典例题 【分析】

从第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。在移动过程中，只要改变一下移动的顺序，而移动的次数不会变。经典例题

参考程序 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 thenbegin inc(s);a[i+1]:=a[i+1]+a[i]-v; end; writeln(s);讨论二 【例6】合并果子（NOIP2004）

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。讨论二

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有3种果子，数目依次为1，2，9。可以先将1，2堆合并，新堆数目为3，耗费体力为3，接着，将新堆与原先的第3堆合并，又得到新的堆，数目为12，耗费体力为12，所以多多总共耗费体力为15。讨论二

【分析】

为了使最终的体力耗费值最小，应该每一次都选择最小的两堆果子合并，使每次合并耗费的体力值最小。

算法过程：

（1）读入每堆果子的数目；

（2）将果子数目按递增顺序进行排序；

（3）合并数目最少的两堆果子，并增加体力耗费值；

（4）在果子序列中删除合并的两堆果子数目，增加合并后的果子数目；

（5）重复步骤2－4，直到所有果子合并为一堆；

（6）输出体力耗费值。讨论二

【分析】

上面的方法需要进行n-1次排序，比较浪费时间，可以用空间换时间的思路，另设一个数组存放每次合并后的堆。

先读入n堆果子的数目a，并按递增顺序进行排列，得到一个序列a[1]……a[n]。

再设另一个数组b，从a、b的第一个元素开始找合并方案：

（1）a数组的两个元素合并；

（2）a和b数组的一个元素合并；

（3）b数组的两个元素合并。

将合并后的值放入b数组。

参考程序

p:=0;x:=1;y:=1;total:=0; fori:=1ton-1do begin min:=maxlongint; ifa[x]+a[x+1]<min thenbeginmin:=a[x]+a[x+1];t:=1;end; ifa[x]+b[y]<min thenbeginmin:=a[x]+b[y];t:=2;end; ifb[y]+b[y+1]<min thenbeginmin:=b[y]+b[y+1];t:=3;end; p:=p+1;b[p]:=min;total:=total+min; ift=1thenx:=x+2; ift=2thenbeginx:=x+1;y:=y+1; ift=3theny:=y+2; end; writeln(total);经典例题【例7】三国游戏（NOIP2010普及组第4题）双方选将过程如下所示：武将相互之间的默契值：12345615281629272233201383226433115126经典例题

【分析】1654323332经典例题

【分析】12345678111111170211118013111501416011511161171818765432经典例题

【分析】12345678111111170211118013111114160501511161171818765432经典例题 【分析】

将所有边按从大到小排序，检查每条边的两个顶点是否已出现过，有三种情况：

（1）两个顶点都没有出现过，说明两个武将都是自由的，不能同时取到，放弃该边；

（2）有一个顶点出现过，说明这个武将前面可以被小涵先取到，现在可以取另一个顶点，该边即为最大值；

（3）两个顶点都出现过，说明这两个武将前面都可以被小涵分别先取到，该边即为最大值。讨论三

【例8】火柴排队（NOIP2013提高组day1第2题）

涵涵有两盒火柴，每盒装有n根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：

，其中ai表示第一列火柴中第i个火柴的高度，bi表示第二列火柴中第i个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对99,999,997取模的结果。 【输入输出样例1】 4 1 2314 3214 【输入输出样例说明】

最小距离是0，最少需要交换1次，比如：交换第1列的前2根火柴或者交换第2列的前2根火柴。 【输入输出样例2】 4 2 1342 1724 【输入输出样例说明】

最小距离是10，最少需要交换2次，比如：交换第1列的中间2根火柴的位置，再交换第2列中后2根火柴的位置。

【分析】

对距离公式化简得：

要求最小，就只需要最大即可。

这里有个贪心，当a1<a2<…<an，b1<b2<…<bn时，

最大。

证明如下：

若存在a>b，c>d，且ac+bd<ad+bc，则a(c-