題目0057–Forest（月亮森林）題目來(lái)源：Ctsc2002推薦者：林希德一、英文原文二、中文翻譯月亮森林一天早晨，一個(gè)小女孩在森林里玩耍時(shí)看到一顆神奇的種子，光芒四射，還散發(fā)著一股淡淡的清香。女孩很喜歡這顆種子，便把它捧在手里帶回了家。那天晚上，女孩做了一個(gè)夢(mèng)，夢(mèng)到一個(gè)面目慈祥的白胡子老爺爺。老爺爺對(duì)她說(shuō)，她手里的種子來(lái)自一棵月亮之樹(shù)，原本只有在月亮上才能見(jiàn)到它，但是機(jī)緣巧合，種子悄悄的落在了地球上，無(wú)法再回到月亮上了。老爺爺發(fā)現(xiàn)女孩兒很喜歡這顆種子，就問(wèn)她是否愿意借助自己的勤勞和智慧，用這顆小小的種子種出一片茂密的月亮森林，讓月亮樹(shù)在地球上有一個(gè)溫暖的新家。女孩興奮地點(diǎn)點(diǎn)頭，忙問(wèn)老爺爺具體應(yīng)該怎么做。老人解釋說(shuō)，這顆種子非同尋常，種下去的第二天上午就會(huì)長(zhǎng)成一棵高度為1(一個(gè)單位)的小樹(shù)苗。月亮樹(shù)的生命力極強(qiáng)，以后還會(huì)每天上午長(zhǎng)高一個(gè)單位。由于月亮樹(shù)不同于地球上的生物，女孩必須使用一種特殊的肥料才能對(duì)它施肥，而這種肥料老爺爺每天會(huì)送給女孩兒一個(gè)單位。每天晚上，她必須給一棵樹(shù)或者下午剛種下去的種子施肥，但不能多施肥，也不能不施肥。被施肥的樹(shù)或者種子在第二天上午將比一般情況下多長(zhǎng)高一個(gè)單位，即兩個(gè)單位。月亮樹(shù)在成長(zhǎng)的過(guò)程中有兩個(gè)稱為“收獲點(diǎn)”的特殊高度，分別為HP1和HP2。當(dāng)月亮之樹(shù)的高度第一次達(dá)到或者超過(guò)HP1的那天中午，樹(shù)上就會(huì)結(jié)出一個(gè)果實(shí)。同樣，當(dāng)高度第一次達(dá)到或者超過(guò)HP2的那天中午，樹(shù)上也會(huì)結(jié)出一個(gè)果實(shí)。果實(shí)里面有一顆種子,和女孩當(dāng)初撿到的一模一樣。每天下午，女孩都可以選擇一些種子種下去，當(dāng)然也可以不種。當(dāng)女孩種了恰好M棵樹(shù)，且它們的高度都相同時(shí)，這些樹(shù)才能真正的適應(yīng)地球的環(huán)境，永遠(yuǎn)的活下去。醒來(lái)后的那天下午，女孩兒就按照老爺爺?shù)姆愿腊逊N子種下去了。她把完成老爺爺交付給她的任務(wù)作為一生中最大的心愿，日復(fù)一日，年復(fù)一年辛勤的勞動(dòng)著。她每天傍晚一坐在門檻上望著遠(yuǎn)方，眼前就會(huì)浮現(xiàn)出一片美麗而寬廣的月亮森林。她堅(jiān)信自己一定能成功，需要再長(zhǎng)的時(shí)間也不怕。但是這一天何時(shí)才會(huì)來(lái)到呢？【輸入文件】輸入文件forest.in僅包含三個(gè)整數(shù)HP1,HP2,M（2<=HP1<HP2<=20,2<=M<=100）,代表兩個(gè)收獲點(diǎn)的高度和所需月亮樹(shù)的棵數(shù)。【輸出文件】輸出文件forest.out僅包含一個(gè)整數(shù)T，即最少需要的天數(shù)。三、初步討論情況侯啟明感覺(jué)標(biāo)程那種貪心法是正確的，但是無(wú)從證明……伍昱感覺(jué)應(yīng)該是標(biāo)程那樣貪姜尚仆貪心，但不知有沒(méi)有證明。高正宇我有點(diǎn)懷疑貪心法?？傆X(jué)得有什么地方值得思考，但是好像又找不到什么錯(cuò)。劉才良對(duì)于測(cè)試數(shù)據(jù)，似乎有人找到了更優(yōu)的解，我不知道如何貪心才能得到最優(yōu)解。方奇按標(biāo)程的貪心，存在反例，更好的算法沒(méi)有想到張?jiān)屏猎趶?fù)旦大學(xué)講課的時(shí)候已經(jīng)有人提出了反例。此問(wèn)題應(yīng)該是NP.張寧這道題目的純貪心法是有問(wèn)題的，問(wèn)題出現(xiàn)在是否對(duì)已達(dá)第一“收獲點(diǎn)”的第一棵樹(shù)施肥，不過(guò)在這一步的處理上采用搜索應(yīng)該沒(méi)有問(wèn)題。金愷Forest的標(biāo)準(zhǔn)程序好像有點(diǎn)問(wèn)題，因?yàn)槲艺{(diào)試某個(gè)測(cè)試點(diǎn)時(shí)，發(fā)現(xiàn)他數(shù)組中的第一棵樹(shù)不是最高的樹(shù)了。饒向榮出題者的意圖是貪心來(lái)做，但是沒(méi)有發(fā)現(xiàn)很好的貪心，經(jīng)過(guò)幾次貪心算法的嘗試，總是有對(duì)應(yīng)的反例?？赡軟](méi)什么正確的貪心算法。周源當(dāng)時(shí)（2002年6月吧）我寫了一個(gè)貪心，很faint的發(fā)現(xiàn)有兩個(gè)測(cè)試點(diǎn)，我的解比stdout的還要優(yōu)，而且我打出了方案，讓W(xué)angTing編了一個(gè)驗(yàn)證程序，顯然答案是對(duì)的。后來(lái)給SrbGa測(cè)試，他說(shuō)是錯(cuò)的，也許是理解不同吧。很可惜的是，我已經(jīng)把我的思路忘掉了，但是還有程序在，有興趣的同學(xué)可以來(lái)找我要，也歡迎來(lái)討論。邵煊程如果給高的樹(shù)施肥，盡管能較快地產(chǎn)出種子，但這也使得今后要使得所有樹(shù)高度都相同比較困難（這棵樹(shù)很高）；如果給矮的樹(shù)施肥，盡管能權(quán)衡高度，但不能較快地產(chǎn)出種子。因此，嚴(yán)密的證明是不可缺少的。何林每次選擇能最早結(jié)出種子的樹(shù)去澆水。假設(shè)這顆樹(shù)不是第一顆，那么肯定沒(méi)問(wèn)題；假如是的呢？我覺(jué)得應(yīng)該分兩種情況討論：給第一棵樹(shù)澆水，剩下的按照上述方法繼續(xù)貪心不給第一顆樹(shù)澆水，給第二快能結(jié)出種子的樹(shù)澆水。時(shí)間復(fù)雜度是o(n^2)，我覺(jué)得肯定能保證正確性。陸可昱盡量少的為第1棵樹(shù)施肥（設(shè)第1棵最高）；盡量快的時(shí)間內(nèi)產(chǎn)生新的種子。這兩個(gè)條件在有的時(shí)候是矛盾的，我現(xiàn)在的想法是通過(guò)枚舉是否為第1棵樹(shù)多施肥（最多需枚舉hp2-hp1次），然后再用貪心做。好像是在貪心的時(shí)候還要注意到：如果兩棵樹(shù)離hp1（或hp2）同樣距離的話，給矮的一棵樹(shù)澆水。林希德定義N是當(dāng)前月亮樹(shù)的數(shù)量，Hi是第i棵樹(shù)的高度，規(guī)定任何時(shí)刻滿足H1H2H3…。別無(wú)選擇，最先總是給第1棵樹(shù)施肥，直到收獲1粒種子。當(dāng)M棵樹(shù)全部被栽種后，往后每天總給最矮的樹(shù)施肥，直到D天以后月亮森林長(zhǎng)成。其中，。因此，在M棵樹(shù)未被全部栽種以前，我們的目標(biāo)是：盡快收獲種子（種子一旦收獲立即播種），而又不讓第1棵樹(shù)長(zhǎng)得太高。假設(shè)當(dāng)前第1棵樹(shù)的高度介于HP1和HP2之間，那么給樹(shù)1施肥會(huì)有怎樣的影響呢？好處是可以讓第x=N+1棵樹(shù)盡快發(fā)芽，這樣D值減少1；還有就是連鎖反應(yīng)，因?yàn)楸M快發(fā)芽利于盡快結(jié)果。壞處是根據(jù)D值計(jì)算公式，D值會(huì)增加M-1。其實(shí)，與其將結(jié)果的期望寄托在第x棵樹(shù)上，不如將它寄托在某棵高度<HP1的樹(shù)y上（y一定存在），因?yàn)閥比x更容易結(jié)出果實(shí)，并且無(wú)論給y施肥還是給x施肥都不改變D值。綜上，好處是D值減1，壞處是D值加M–1，好處<壞處。故，我們規(guī)定：一旦收獲第1粒種子，從此永不給第1棵樹(shù)施肥。假設(shè)a是滿足Ha<HP1的最高的樹(shù)，而b是滿足Hb<HP2的最高的樹(shù)。如果HP1-Ha<HP2–Hb，那么為了盡快收獲種子，我們給樹(shù)a施肥；如果HP1-Ha>HP2–Hb，那么為了盡快收獲種子，我們給樹(shù)b施肥；如果HP1-Ha=HP2–Hb，那么因?yàn)榻oa施肥，利于a在HP1和HP2兩個(gè)生長(zhǎng)點(diǎn)結(jié)果，而給b施肥，只利于b在HP2一個(gè)生長(zhǎng)點(diǎn)結(jié)果，所以，從長(zhǎng)遠(yuǎn)利益著想，我們給樹(shù)a施肥。5）下面給出程序基本框架：所有Hi清零；Day=(HP1+1)div2，N=1，Seed=1，H1=Day2；WhileＮ+Seed<Mdo｛判斷是否Ｍ棵樹(shù)已全部栽種｝Ｎ=Ｎ＋Seed，Day=Day+1，Ｃ=N，Seed=0；｛播種，天數(shù)增加｝Fori=1NdoHi=Hi+1；｛樹(shù)長(zhǎng)高１個(gè)單位｝IfHi=HP1或者Hi=HP2ThenSeed=Seed+1；｛判斷是否有種子收獲｝IfHi<HP1ThenFi=HP1–Hi｛計(jì)算樹(shù)高度離收獲點(diǎn)的距離｝ElseIfHi<HP2ThenFi=HP2–HiElseFi=+；EndforFori=N2do｛找出離收獲點(diǎn)最近的那棵樹(shù)｝IfFi<FcThenC=i；WhileC>2并且Hc=Hc-1doC=C–1；｛保持樹(shù)高度非遞增性｝Hc=Hc+1；｛施肥｝IfHc=HP1或者Hc=HP2ThenSeed=Seed+1；｛再次判斷是否有種子收獲｝Endwhile計(jì)算Ｄ值，輸出Day+D作為最終答案；劉汝佳：大家試