集訓(xùn)隊(duì)作業(yè)coins解題報(bào)告

《Coins》解題報(bào)告仇榮琦【題目來源】BalticOlympiadinInformatics2006【題目描述】有一個(gè)國家，流通著N種面值的硬幣，其中包括了1分硬幣。另外，有一種面值為K分的紙幣，它超過了所有硬幣的面值。有一位硬幣收藏家，他想收集每一種面值的硬幣樣本。他家里已經(jīng)有一些硬幣，但是現(xiàn)在他只帶著一張K分紙幣去商店。商店里總共有K-1種商品，價(jià)格分別為1分、2分……K-1分。這家商店使用以下算法找零：假設(shè)總共需要找A分；尋找最高的不超過A的硬幣面值，設(shè)它為B分硬幣；給顧客一枚B分硬幣，然后令A(yù)A-B；如果A=0，算法結(jié)束；否則轉(zhuǎn)2。收藏家想用他的K分紙幣買一件商品。請(qǐng)你編寫程序，計(jì)算：收藏家能夠得到多少種他還沒有過的硬幣？在滿足上一問的前提下，他能夠買的最貴的商品是什么？【輸入格式】第一行為兩個(gè)整數(shù)N(1≤N≤500000)和K(2≤K≤1000000000)。以下N行描述流通的硬幣。第i+1行包含兩個(gè)整數(shù)ci(1≤ci<K)和di，其中ci表示第i枚硬幣的面值；di=1表示收藏家已經(jīng)擁有了這枚硬幣，di=0表示他還沒有。硬幣是以面值升序給出的，即c1<c2<…<cn。另外，第一枚硬幣一定是1分，即c1=1?！据敵龈袷健康谝恍袨橐粋€(gè)整數(shù)，表示收藏家最多能獲得多少種之前還沒有的硬幣。第二行為一個(gè)整數(shù)，表示在前一問的前提下，收藏家能購買的最貴的商品價(jià)格?！据斎霕永?2510203150100130200【輸出樣例】36【題目分析】題目的大意是：一位收藏家用一張K分的紙幣去買小于K分的任意商品。商店有N種硬幣，找零時(shí)使用的是貪心算法——盡量選大面值。求最多能夠得到的之前沒有的硬幣種數(shù)。首先分析簡(jiǎn)單的情況：收藏家一種硬幣都沒有。也就是說，所有的硬幣都是需要的?？紤]找零總數(shù)為A的某種找零方案（不一定是商店采用的方案），設(shè)Si表示c1,c2,…,ci在方案中出現(xiàn)的硬幣總價(jià)值。我們可以得出以下的結(jié)論：某種找零方案是商店采用的方案當(dāng)且僅當(dāng)Si<ci+1(1≤i<N)且SN<K。證明：命題的充分性是顯然的，關(guān)鍵是證明必要性。易知Si是單調(diào)不減的，即S1≤S2≤…≤SN。假設(shè)找零方案中總共出現(xiàn)了tot種硬幣，分別為。考慮商店找零算法第一次選硬幣的過程，有，而，所以商店一定會(huì)選擇硬幣，即該方案中的第tot枚硬幣與商店的選擇相同。假設(shè)商店找零算法前i-1次選出的硬幣分別為，那么商店在第i次選硬幣時(shí)，還需要找零的總數(shù)，而，所以商店一定會(huì)選擇硬幣。綜上所述，這種方案是商店采用的方案。這個(gè)結(jié)論指出了商店采用方案的本質(zhì)特征。題目要求買價(jià)格小于K的最貴的商品，即找的零錢是最少的。因此我們可以得出下面的結(jié)論：在收藏家最優(yōu)購買策略中，任何一枚硬幣在商店找零方案中最多出現(xiàn)一次。證明：假設(shè)收藏家購買價(jià)格為W的商品是最優(yōu)的，即找零的總數(shù)為K-W，而其中出現(xiàn)了x次硬幣ck(x>1)，那么他可以購買價(jià)格為W+(x-1)ck的商品，即找零的總數(shù)為K-W-(x-1)ck，此時(shí)的商店找零方案仍然是可行的，并且與前一種策略的找零方案相比僅僅少了(x-1)枚硬幣ck。顯然，后一種策略讓收藏家獲得的硬幣種數(shù)不變，但購買的價(jià)格比前者大，因而更優(yōu)。這與假設(shè)不符。有了這個(gè)結(jié)論，我們很容易可以得到下面的貪心算法。按面值從小到大考慮每一種硬幣是否在找零中。如果選擇當(dāng)前硬幣后，所有已選硬幣的面值之和小于下一枚硬幣面值（或者小于K，如果當(dāng)前考慮最后一枚硬幣），那么選擇當(dāng)前硬幣；否則不選?，F(xiàn)在我們回歸到原問題。加上“收藏家初始時(shí)有若干枚硬幣”的條件后，只需對(duì)算法進(jìn)行一點(diǎn)改動(dòng)：考慮每一枚硬幣時(shí)，如果收藏家初始時(shí)有當(dāng)前硬幣，那么不選。證明可以仿照上面的方式進(jìn)行。另外，有一種特殊情況需要單獨(dú)判斷：如果初始時(shí)收藏家已經(jīng)有所有種類的硬幣，根據(jù)題意他最多只能買價(jià)格為K-1的商品，而根據(jù)以上算法會(huì)得到買價(jià)格為K的商品的結(jié)論。具體實(shí)現(xiàn)的時(shí)候，直接令第N+1枚硬幣的面值為K，可以簡(jiǎn)化一些判斷。如果采用邊讀入邊處理并使用滾動(dòng)數(shù)組，可以將空間復(fù)雜度將為O(1)?！拘阅芊治觥繒r(shí)間復(fù)雜度：O(N)空間復(fù)雜度：O(1)編程復(fù)雜度：低【總結(jié)】題目的核心條件是：商店的找零規(guī)則是一個(gè)貪心過程。因此，解題時(shí)應(yīng)著重分析這一規(guī)則隱含的信息，從而巧妙地設(shè)計(jì)出貪心算法?！驹创a】見附件coins.pasprogramcoins;constmaxn=500001;varn,k,o,ot:longint;value:array[boolean]oflongint;{滾動(dòng)數(shù)組，表示各硬幣的面值}al:array[boolean]ofboolean;{滾動(dòng)數(shù)組，表示初始時(shí)收藏家已經(jīng)擁有的硬幣}procedureinit;{讀入數(shù)據(jù)}beginreadln(n,k);end;proceduremain;{主過程}vari,te,s:longint;beginfillchar(value,sizeof(value),0);fillchar(al,sizeof(al),0);s:=0;o:=0;readln(value[odd(1)],te);al[odd(1)]:=te=1;fori:=2ton+1dobeginifi=n+1thenvalue[odd(i)]:=kelsebeginreadln(value[odd(i)],te);al[odd(i)]:=te=1;end;ifal[notodd(i)]thencontinue;ifs+value[notodd(i)]>=value[odd(i)]thencontinue;inc(o);s:=s+value[notodd(i)];end;ifs=0thens:=1;{特殊情況：收藏家初始時(shí)擁有所有硬幣}ot:=k-s;end;procedureprint;{輸出過程}beginwriteln(o);writeln(ot);end;beginassign(input,'coins.in');reset(input);assign(output,'coins.out');rewrite(output);init;main;print;close(input);close(output);end.【英文原題】COINCOLLECTORInacertaincountry,thereareNdenominationsofcoinsincirculation,includingthe1-centcoin.Additionally,there’sabillwhosevalueofKcentsisknowntoexceedanyofthecoins.There’sacoincollectorwhowantstocollectaspecimenofeachdenominationofcoins.Healreadyhasafewcoinsathome,butcurrentlyheonlycarriesoneK-centbillinhiswallet.He’sinashopwherethereareitemssoldatallpriceslessthanKcents(1cent,2cents,3cents,…,K-1cents).Inthisshop,thechangeisgivenusingthefollowingalgorithm:1.LettheamountofchangetogivebeAcents.2.FindthehighestdenominationthatdoesnotexceedA.(LetitbetheB-centcoin.)3.GivethecustomeraB-centcoinandreduceAbyB.4.IfA=0,thenend;otherwisereturntostep2.Thecoincollectorbuysoneitem,payingwithhisK-centbill.Yourtaskistowriteaprogramthatdetermines:Howmanydifferentcoinsthatthecollectordoesnotyethaveinhiscollectioncanheacquirewiththistransaction?Whatisthemostexpensiveitemthestorecansellhimintheprocess?INPUTTheinputisreadfromatextfilenamedcoins.in.ThefirstlineoftheinputfilecontainstheintegersN(1≤N≤500000)andK(2≤K≤1000000000).ThefollowingNlinesdescribethecoinsincirculation.The(i+1)-thlinecontainstheintegersci(1≤ci<K)anddi,whereciisthevalue(incents)ofthecoin,anddiis1,ifthecollectoralreadyhasthiscoin,or0,ifhedoesnot.Thecoinsaregivenintheincreasingorderofvalues,thatis,c1<c2<…<cN.Thefirstcoinisknowntobethe1-centcoin,thatis,c1=1.OUTPUTTheoutputiswrittenintoatextfilenamedcoins.out.Thefirstlineoftheoutputfileshouldcontainasingleinteger—themaximalnumberofdenominationsthatthecollectordoesnotyethave,butcouldacquirewithasinglepurchase.Thesecondlineoftheoutput