《花生采摘》解題報告.doc

《《花生采摘》解題報告.doc》由會員分享，可在線閱讀，更多相關(guān)《《花生采摘》解題報告.doc（5頁珍藏版）》請在裝配圖網(wǎng)上搜索。

《花生采摘》解題報告 By sx349 【摘要】 核心算法思想：貪心 主要數(shù)據(jù)結(jié)構(gòu)： 其他輔助知識： 時間復(fù)雜度： 空間復(fù)雜度： 【題目大意】 給定一個非空矩陣，每次都從中選擇一個最大值并將其從矩陣中排除，將這些取出的數(shù)排序后計算其花費(fèi)（相鄰兩數(shù)的花費(fèi)是其在矩陣之間的曼哈頓距離），求在給定最大花費(fèi)下，能取到的最大值的最大總和。 【算法分析】 文中說道：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此類推，不過你一定要在我限定的時間內(nèi)回到路邊?！? 根據(jù)這一句話，我們直接就可以得出，這道題應(yīng)該采用貪心的算法。 因此，我們先對數(shù)據(jù)進(jìn)行從大到小的排序，然后每次都取其中的最大值。因為必須在規(guī)定的時間內(nèi)回到路邊，所以在每次取最大值時，首先判斷在采摘了這一次之后是否有足夠的時間回到路邊，即(去采摘目標(biāo)花生的時間)+(采摘那目標(biāo)花生所用的1單位時間)+(從目標(biāo)所在地往第一行的時間)<=(剩下的單位時間)。若條件不滿足就停止，若滿足就繼續(xù)采摘。 由于去摘花生必須從路邊進(jìn)入花生田和從花生田出來，所以我們可以先減去2個單位時間，再將剩下的時間進(jìn)行模擬。 【心得體會】 花生采摘是一道典型的貪心問題，也是一道典型的簡單題（因此這道題的算法分析也只能這樣簡單了……）。但是這道題有一個區(qū)別于其他問題的地方：在解決問題的過程中，主要部分（連續(xù)取最大值）的時間復(fù)雜度只需要，而排序卻花費(fèi)了的時間復(fù)雜度。 這一點(diǎn)確實是在許多情況下無法回避的一個問題。我一直記得我們平時上課的計算機(jī)書上有一個簡單的例子：給你一些電話號碼，讓你去尋找某一個指定的號碼。書上的解釋是用二分查找，但是我們來考慮一下，二分查找合適嗎？當(dāng)然，如果是在有序的情況下，二分的復(fù)雜度是，但是，在無序的情況下，二分必須要在排序好后才能解決，那么時間復(fù)雜度就上升到了，因為除了少部分特殊的排序之外，因此不可避免地導(dǎo)致了的排序復(fù)雜度。如此一來，就超過了順序查找的復(fù)雜度了。難道排序的合理性就此受到了質(zhì)疑了嗎？當(dāng)然不是，如果是查找多次的話，二分查找的時間復(fù)雜度就是，而順序查找則飆升到了。由此我們可以得出這樣一個結(jié)論：預(yù)處理操作的效率隨著預(yù)處理所得到的數(shù)據(jù)的使用率的提高而提高。 這又引出了這樣一個怪異的想法：如果我找到了針對某個問題的一個時間復(fù)雜度僅為的主算法，那么我是不是就一定能解決它呢？顯然不是。如果這個問題的輸入達(dá)到了上千萬乃至上億，單單讀入的復(fù)雜度就已經(jīng)使程序罷工了。同樣的，我也曾經(jīng)有過因為輸出過多而導(dǎo)致超時的經(jīng)歷。 因此，輸入、輸出、排序乃至其他一些游離于主算法之外的東西，有時反而成為了一個問題的決定點(diǎn)，這種出人意料的場景也著實是值得我們思考的。 【附錄】 2005選拔賽第一輪 花生采摘 peanuts.pas/dpr/c/cpp 輸入文件名：peanuts .in 輸出文件名：peanuts.ou 【問題描述 】 魯濱遜先生有一只寵物猴，名叫多多。這天，他們兩個正沿著鄉(xiāng)間小路散步，突然發(fā)現(xiàn)路邊的告示牌上貼著一張小小的紙條：“歡迎免費(fèi)品嘗我種的花生！——熊字”。 魯濱遜先生和多多都很開心，因為花生正是他們的最愛。在告示牌背后，路邊真的有一塊花生田，花生植株整齊地排列成矩形網(wǎng)絡(luò)（如圖1）。有經(jīng)驗的多多一眼就能看出，每株花生植株下的花生有多少。 為了訓(xùn)練多多的算術(shù)，魯濱遜先生說：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此類推，不過你一定要在我限定的時間內(nèi)回到路邊。” 2 4 6 5 1 3 7 1 3 4 6 2 5 路 圖1 2 4 6 5 1 3 7 1 3 4 6 2 5 路 圖2 15 13 7 9 我們假定多多在每個單位時間內(nèi)，可以做下列四件事情中的一件： 1） 從路邊跳到最靠近路邊（即第一行）的某棵花生植株； 2） 從一棵植株跳到前后左右與之相鄰的另一棵植株； 3） 采摘一棵植株下的花生； 4） 從最靠近路邊（即第一行）的某棵花生植株跳回到路邊。 現(xiàn)在給定一塊花生田的大小和花生的分布，請問在限定的時間內(nèi)，多多最多可以采到多少個花生？注意可能只有部分的植株下面長有花生，假設(shè)這些植株下的花生個數(shù)各不相同。 例如在圖二所示的花生田里，只有位于（2，5），（3，7），（4，2），（5，4）的植株下長有花生，個數(shù)分別為13，7，15，9。沿著圖示的路線，多多在21個單位時間內(nèi)，最多可以采到37個花生。 [輸入文件] 輸入文件peanuts.in的第一行包括三個整數(shù)，M，N和K，用空格隔開；表示花生田的大小為M*N（1<=M，N<=20），多多采花生的限定時間為K（0<=K<=1000）個單位時間. 接下來的M行,每行包括N個非負(fù)整數(shù),也用空格隔開; 第i+1行的第j個整數(shù)Pij(0<=Pij<=500)表示花生田里植株(i,j)下花生的數(shù)目,0表示該植株下沒有花生。 [輸出文件] 輸出文件peanuts.out包括一行. 這一行只包含一個整數(shù)，即在限定時間內(nèi)，多多最多可以采到的花生的個數(shù)。 [樣例輸入] 6 7 21 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 [樣例輸出1] 37 [樣例輸入2] 6 7 20 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 [樣例輸出2] 28 【源程序清單】 { PROG: Peanuts LANG: PASCAL ID: xyj-flash } Program Peanuts; Var X,Y,Value:Array[0.400] of Longint; Map:Array[1..20,1..20] of Longint; M,N,K,I,J,Top,T,Sum:Longint; Procedure Sort(L,R:Longint); Var I,J,Mid:Longint; Begin I:=L;J:=R;Mid:=Value[(L+R) Div 2]; Repeat While Value[I]>Mid do Inc(I); While Value[J]J; If I0 Then Begin Inc(Top); Value[Top]:=Map[I,J]; X[Top]:=I;Y[Top]:=J; End; End; Sort(1,Top); K:=K-2; X[0]:=1;Y[0]:=Y[1]; T:=0;I:=1;Sum:=0; While TK Then Print(Sum); Sum:=Sum+Value[I]; T:=T+X[I]-1; Inc(I); End; End.