信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用

基于貪心的算法和應(yīng)用1信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本貪心算法引入 【引例1】在n行m列的正整數(shù)矩陣中，要求從每行中選出1個(gè)數(shù)，使得選出的總共n個(gè)數(shù)的和最大。 【分析】要使總和最大，則每個(gè)數(shù)要盡可能大，自然應(yīng)該選每行中最大的那個(gè)數(shù)。2信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本貪心算法引入 【引例2】有1元、5元、10元、50元、100元、500元的硬幣各C1、C5、C10、C50、C100、C500枚?，F(xiàn)在要用這些硬幣來(lái)支付A元，最少需要多少枚硬幣？ 【分析】?jī)?yōu)先使用面值大的硬幣。3信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本貪心算法定義

貪心算法是從問(wèn)題的某一個(gè)初始狀態(tài)出發(fā)，通過(guò)逐步構(gòu)造最優(yōu)解的方法向給定的目標(biāo)前進(jìn)，并期望通過(guò)這種方法產(chǎn)生出一個(gè)全局最優(yōu)解的方法。

小球表示當(dāng)前狀態(tài),

紅箭頭表示當(dāng)前最優(yōu)決策；

藍(lán)箭頭表示其他決策。

方向4信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本貪心算法的特點(diǎn)

貪心標(biāo)準(zhǔn)選擇：所謂貪心標(biāo)準(zhǔn)選擇就是應(yīng)用當(dāng)前“最好”的標(biāo)準(zhǔn)作為統(tǒng)一標(biāo)準(zhǔn)，將原問(wèn)題變?yōu)橐粋€(gè)相似的但規(guī)模更小的子問(wèn)題，而后的每一步都是當(dāng)前看似最佳的選擇。

最優(yōu)子結(jié)構(gòu)：當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。5信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本貪心算法的特點(diǎn) 【引例3】部分背包問(wèn)題

有一個(gè)背包，容量是M＝150，有7個(gè)物品，物品可以分割成任意大小，要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘?。物品ABCDEFG體積35306050401025價(jià)值104030503540306信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本貪心算法的特點(diǎn) 【分析】

有以下幾種策略可供選擇： （1）每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？ （2）每次挑選所占空間最小的物品裝入是否能得到最優(yōu)解？ （3）每次選取單位容量?jī)r(jià)值最大的物品。7信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本貪心算法的特點(diǎn)

解題一般步驟: 1、設(shè)計(jì)數(shù)據(jù)找規(guī)律；

2、進(jìn)行貪心猜想；

3、正確性證明（嚴(yán)格證明和一般證明） ★一般證明：列舉反例； ★嚴(yán)格證明：數(shù)學(xué)歸納和反證法；

4、程序?qū)崿F(xiàn)。8信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題※刪數(shù)問(wèn)題（NOI1995）※取數(shù)問(wèn)題（IOI1996）※接水問(wèn)題※最大整數(shù)※均分紙牌（NOIP2002）※三國(guó)游戲（NOIP2010）※火柴排隊(duì)（NOIP2013）9信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題 【例1】刪數(shù)問(wèn)題（NOI1994） 鍵盤輸入一個(gè)高精度的正整數(shù)N，去掉其中任意S個(gè)數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。 輸出剩下的最小數(shù)。10信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題 【分析】

因?yàn)橐獎(jiǎng)h除S個(gè)數(shù)字，可以一個(gè)一個(gè)地刪，每一次刪除的目的都是使剩下的數(shù)盡量小。 那么在每一次刪除時(shí)，應(yīng)該選擇哪個(gè)數(shù)字呢？最大的那個(gè)數(shù)字？還是最左邊的那個(gè)數(shù)字？例如5768，刪除7可以使剩余的數(shù)最小。//刪除7會(huì)使后面的較小數(shù)前移，從而得到更小的數(shù)。如果不刪除7，刪除之前的較小數(shù)，會(huì)使大數(shù)7前移。刪除7之后的較小數(shù)，則比刪除7這個(gè)較大數(shù)得到的數(shù)要大。11信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題

結(jié)論： 每一次刪除的數(shù)字應(yīng)該是這個(gè)數(shù)字序列中最左邊遞減序列的第一個(gè)數(shù)字。具體操作為，按高位到低位的方向搜索遞減區(qū)間。若不存在遞減區(qū)間，則刪除尾數(shù)字，否則刪除遞減區(qū)間的首數(shù)符，這樣就形成一個(gè)最小的數(shù)。 重復(fù)上述規(guī)則，直到刪除S個(gè)數(shù)字為止。12信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題

例如：N＝8796542，S＝4

第一次：N＝8796542，刪除8； 第二次：N＝796542，刪除9； 第三次：N＝76542，刪除7； 第四次：N＝6542，刪除6，得到542。13信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題

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信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本討論一 【例2】取數(shù)問(wèn)題（IOI1996） 給出2n（n≤100）個(gè)自然數(shù)（小于等于30000），將這2n個(gè)自然數(shù)排成一列，游戲雙方A和B從中輪流取數(shù)，只允許從兩端取數(shù)，A方先取，然后B方再取。取完時(shí)，誰(shuí)取的數(shù)字總和最大為取勝方；若雙方和相等，則B勝，試問(wèn)A方是否有必勝策略？15信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本討論一

輸入格式：兩行，第一行一個(gè)整數(shù)n，第二行有2n個(gè)自然數(shù)。 輸出格式：只有一行，若A有必勝策略，則輸出“YES”，否則輸出“NO”。 輸入樣例：

4 79364253

輸出樣例：

YES16信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本討論一 【分析】

若采用這樣一種策略，讓A方每次取數(shù)列兩端較大的那個(gè)數(shù)，則B方也會(huì)這樣取，對(duì)于樣例：79364253，

A方會(huì)取得7、3、4、5，

B方會(huì)取得9、6、2、3，

A方的總和為19，B方的總和為20，按照規(guī)則，輸出“NO”。17信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本討論一 【分析】

如果A方取走奇數(shù)位置上的數(shù)后，剩下的兩端都是偶數(shù)位置上的數(shù)，如果A方取走偶數(shù)位置上的數(shù)后，剩下的兩端都是奇數(shù)位置上的數(shù)。

A方既可以取走所有奇數(shù)位置上的數(shù)，或者取走所有偶數(shù)位置上的數(shù)。 另一個(gè)策略：讓A方取“數(shù)和較大的奇（或偶）位置上的所有數(shù)”。18信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本討論一

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信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題 【例3】排隊(duì)接水 有n個(gè)人在一個(gè)水龍頭前排隊(duì)接水，假如每個(gè)人接水的時(shí)間為Ti，請(qǐng)編程找出這n個(gè)人排隊(duì)的一種順序，使得這n個(gè)人平均等待時(shí)間最小。 輸入樣例：

10 56121991000234335599812

輸出樣例：

291.9020信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題 【分析】

平均等待時(shí)間就是每個(gè)人的等待時(shí)間之和再除以n，因?yàn)閚是常數(shù)，所以等待時(shí)間之和最小也就等同于平均等待時(shí)間最小。 Total=Ti1+(Ti1+Ti2)+(Ti1+Ti2+Ti3)+…(Ti1+Ti2+…+Tin) =nTi1+(n-1)Ti2+(n-2)Ti3+…+Tin

如果讓Ti1最小，Ti2次小，…，Tin最大，也就是把接水時(shí)間少的人盡可能排在前面，總的等待時(shí)間就最少了。21信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題 【例4】最大整數(shù) 設(shè)有n個(gè)正整數(shù)(n<=20,Longint范圍內(nèi)),將它們聯(lián)接成一排組成一個(gè)最大的多位整數(shù)。 例如:n=3時(shí),3個(gè)整數(shù)13,312,343聯(lián)接成的最大整數(shù)為:34331213。 又如:n=4時(shí),4個(gè)整數(shù)7,13,4,246聯(lián)接成的最大整數(shù)為:7424613。 程序輸入:n及n個(gè)數(shù)。 程序輸出:聯(lián)接成的多位數(shù)。22信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題 【分析】

本例因?yàn)樯婕皩蓚€(gè)自然數(shù)連接起來(lái)的問(wèn)題，采用字符串來(lái)處理比較方便。首先我們自然會(huì)想到大的字符串應(yīng)該排在前面，因?yàn)槿绻鸄與B是兩個(gè)由數(shù)字字符構(gòu)成的字符串且A>B，一般情況下有A+B>B+A，但是當(dāng)A=B+C時(shí)，按字符串的大小定義有A>B，但有可能會(huì)出現(xiàn)A+B<B+A的情況，如A=121,B=12,則A+B=12112,B+A=12121,A+B<B+A。23信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題【分析】

根據(jù)題意用另一種字符串比較辦法，將A+B與B+A相比較，如果前者大于后者，則認(rèn)為A>B，按這一定義將所有的數(shù)字字符串從大到小排序后連接起來(lái)所得到的數(shù)字字符串即是問(wèn)題的解。排序時(shí)先將所有字符串中的最大值選出來(lái)存在數(shù)組的第一個(gè)元素中，再?gòu)牡诙磷詈笠粋€(gè)元素中最大的字符串選出來(lái)存在數(shù)組的第二個(gè)元素中，直到從最后兩個(gè)元素中選出最大的字符串存在數(shù)組的倒數(shù)第二個(gè)元素中為止。24信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題

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信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題 【例5】均分紙牌（NOIP2002） 有N堆紙牌，編號(hào)分別為1，2，……，N。第i堆有a[i]張紙牌（a[i]≤10000）,但紙牌總數(shù)必為N的倍數(shù)。可以在任一堆上取若干張紙牌，然后移動(dòng)。移牌規(guī)則為：在編號(hào)為1堆上取的紙牌，只能移到編號(hào)為2的堆上；在編號(hào)為N的堆上取的紙牌，只能移到編號(hào)為N－1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動(dòng)方法，用最少的移動(dòng)次數(shù)使每堆牌數(shù)都一樣多。26信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題

例如：N＝4，紙牌數(shù)分別為9、8、17、6，移動(dòng)3次可達(dá)到目的。 第一次：從第3堆取4張牌放到第4堆；

9、8、13、10

第二次：從第3堆取3張牌放到第2堆；

9、11、10、10

第三次：從第2堆取1張牌放到第1堆。

10、10、10、1027信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題 【分析】

設(shè)v為均分后每堆紙牌的張數(shù)，s為最少移動(dòng)次數(shù)。按照從左到右的順序移動(dòng)紙牌。如果第i堆的紙牌數(shù)a[i]不等于v，則移動(dòng)一次，分兩種情況移動(dòng)： （1）如果a[i]>v，則將a[i]-v張紙牌從第i堆移動(dòng)到第i+1堆； （2）如果a[i]<v，則將v-a[i]張紙牌從第i+1堆移動(dòng)第i堆。28信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題 【分析】

從第i+1堆中取出紙牌給第i堆的過(guò)程中，可能會(huì)出現(xiàn)第i+1堆的紙牌數(shù)小于0的情況。如n＝3，三堆紙牌數(shù)為1、2、27，v＝10，要從第2堆移動(dòng)9張紙牌到第1堆，而第2堆只有2張紙牌可以移動(dòng)。按照規(guī)則會(huì)得到10、-7、27，再?gòu)牡?堆移動(dòng)17張紙牌到第2堆，即得到10、10、10。在移動(dòng)過(guò)程中，只要改變一下移動(dòng)的順序，而移動(dòng)的次數(shù)不會(huì)變。29信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題 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//如果之前的調(diào)整使得值正好為v，不用移動(dòng) thenbegin inc(s);a[i+1]:=a[i+1]+a[i]-v; end; writeln(s);30信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本討論二【例6】三國(guó)游戲（NOIP2010普及組第4題）

小涵很喜歡電腦游戲，這些天他正在玩一個(gè)叫做《三國(guó)》的游戲。

在游戲中，小涵和計(jì)算機(jī)各執(zhí)一方，組建各自的軍隊(duì)進(jìn)行對(duì)戰(zhàn)。游戲中共有N位武將（N為偶數(shù)且不小于4），任意兩個(gè)武將之間有一個(gè)“默契值”，表示若此兩位武將作為一對(duì)組合作戰(zhàn)時(shí)，該組合的威力有多大。游戲開始前，所有武將都是自由的（稱為自由武將，一旦某個(gè)自由武將被選中作為某方軍隊(duì)的一員，那么他就不再是自由31信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本討論二

武將了），換句話說(shuō)，所謂的自由武將不屬于任何一方。游戲開始，小涵和計(jì)算機(jī)要從自由武將中挑選武將組成自己的軍隊(duì)，規(guī)則如下：小涵先從自由武將中選出一個(gè)加入自己的軍隊(duì)，然后計(jì)算機(jī)也從自由武將中選出一個(gè)加入計(jì)算機(jī)方的軍隊(duì)。接下來(lái)一直按照“小涵→計(jì)算機(jī)→小涵→……”的順序選擇武將，直到所有的武將被雙方均分完。然后，程序自動(dòng)從雙方軍隊(duì)中各挑出一對(duì)默契值最高的武將組合代表自己的軍隊(duì)進(jìn)行二對(duì)二比武，擁有更高默契值的一對(duì)武將組合獲勝，表示兩軍交戰(zhàn)，擁有獲勝武將組合的一方獲勝。32信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本討論二

已知計(jì)算機(jī)一方選擇武將的原則是盡量破壞對(duì)手下一步將形成的最強(qiáng)組合，它采取的具體策略如下：任何時(shí)刻，輪到計(jì)算機(jī)挑選時(shí)，它會(huì)嘗試將對(duì)手軍隊(duì)中的每個(gè)武將與當(dāng)前每個(gè)自由武將進(jìn)行一一配對(duì)，找出所有配對(duì)中默契值最高的那對(duì)武將組合，并將該組合中的自由武將選入自己的軍隊(duì)。

下面舉例說(shuō)明計(jì)算機(jī)的選將策略，例如，游戲中一共有6個(gè)武將，他們相互之間的默契值如下表所示33信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本討論二

雙方選將過(guò)程如下所示：雙方選將過(guò)程如下所示：武將相互之間的默契值：34信息學(xué)奧賽NOIP教程基于貪心的算法和應(yīng)用5/8/2024點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本討論二

小涵想知道，如果計(jì)算機(jī)在一局游戲中始終堅(jiān)持上面這個(gè)策略，那么自己有沒(méi)有可能必勝？如果有，在所有可能的勝利結(jié)局中，自己那對(duì)用于比武的武將組合的默契值最大是多少？