花生采摘解題報告

1、花生采摘解題報告By sx349 【摘要】核心算法思想：貪心主要數(shù)據(jù)結構：其他輔助知識：時間復雜度：空間復雜度：【題目大意】給定一個非空矩陣，每次都從中選擇一個最大值并將其從矩陣中排除，將這些取出的數(shù)排序后計算其花費（相鄰兩數(shù)的花費是其在矩陣之間的曼哈頓距離），求在給定最大花費下，能取到的最大值的最大總和。【算法分析】文中說道：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此類推，不過你一定要在我限定的時間內回到路邊。”根據(jù)這一句話，我們直接就可以得出，這道題應該采用貪心的算法。因此，我們先對數(shù)據(jù)進行從大到小的排序，然后每次都取其中的最大值。因為

2、必須在規(guī)定的時間內回到路邊，所以在每次取最大值時，首先判斷在采摘了這一次之后是否有足夠的時間回到路邊，即(去采摘目標花生的時間)+(采摘那目標花生所用的1單位時間)+(從目標所在地往第一行的時間)<=(剩下的單位時間)。若條件不滿足就停止，若滿足就繼續(xù)采摘。由于去摘花生必須從路邊進入花生田和從花生田出來，所以我們可以先減去2個單位時間，再將剩下的時間進行模擬?！拘牡皿w會】花生采摘是一道典型的貪心問題，也是一道典型的簡單題（因此這道題的算法分析也只能這樣簡單了）。但是這道題有一個區(qū)別于其他問題的地方：在解決問題的過程中，主要部分（連續(xù)取最大值）的時間復雜度只需要，而排序卻花費了的時間復雜度

3、。這一點確實是在許多情況下無法回避的一個問題。我一直記得我們平時上課的計算機書上有一個簡單的例子：給你一些電話號碼，讓你去尋找某一個指定的號碼。書上的解釋是用二分查找，但是我們來考慮一下，二分查找合適嗎？當然，如果是在有序的情況下，二分的復雜度是，但是，在無序的情況下，二分必須要在排序好后才能解決，那么時間復雜度就上升到了，因為除了少部分特殊的排序之外，因此不可避免地導致了的排序復雜度。如此一來，就超過了順序查找的復雜度了。難道排序的合理性就此受到了質疑了嗎？當然不是，如果是查找多次的話，二分查找的時間復雜度就是，而順序查找則飆升到了。由此我們可以得出這樣一個結論：預處理操作的效率隨著預處理所

4、得到的數(shù)據(jù)的使用率的提高而提高。這又引出了這樣一個怪異的想法：如果我找到了針對某個問題的一個時間復雜度僅為的主算法，那么我是不是就一定能解決它呢？顯然不是。如果這個問題的輸入達到了上千萬乃至上億，單單讀入的復雜度就已經使程序罷工了。同樣的，我也曾經有過因為輸出過多而導致超時的經歷。因此，輸入、輸出、排序乃至其他一些游離于主算法之外的東西，有時反而成為了一個問題的決定點，這種出人意料的場景也著實是值得我們思考的?！靖戒洝?2005選拔賽第一輪 花生采摘 peanuts.pas/dpr/c/cpp 輸入文件名：peanuts .in 輸出文件名：peanuts.ou 【問題描述 】魯濱遜先生有一只

5、寵物猴，名叫多多。這天，他們兩個正沿著鄉(xiāng)間小路散步，突然發(fā)現(xiàn)路邊的告示牌上貼著一張小小的紙條：“歡迎免費品嘗我種的花生！熊字”。魯濱遜先生和多多都很開心，因為花生正是他們的最愛。在告示牌背后，路邊真的有一塊花生田，花生植株整齊地排列成矩形網(wǎng)絡（如圖1）。有經驗的多多一眼就能看出，每株花生植株下的花生有多少。為了訓練多多的算術，魯濱遜先生說：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此類推，不過你一定要在我限定的時間內回到路邊。”2465137134625路圖12465137134625路圖2151379我們假定多多在每個單位時間內，可以做下列

6、四件事情中的一件：1） 從路邊跳到最靠近路邊（即第一行）的某棵花生植株；2） 從一棵植株跳到前后左右與之相鄰的另一棵植株；3） 采摘一棵植株下的花生；4） 從最靠近路邊（即第一行）的某棵花生植株跳回到路邊。現(xiàn)在給定一塊花生田的大小和花生的分布，請問在限定的時間內，多多最多可以采到多少個花生？注意可能只有部分的植株下面長有花生，假設這些植株下的花生個數(shù)各不相同。例如在圖二所示的花生田里，只有位于（2，5），（3，7），（4，2），（5，4）的植株下長有花生，個數(shù)分別為13，7，15，9。沿著圖示的路線，多多在21個單位時間內，最多可以采到37個花生。輸入文件輸入文件peanuts.in的第一行包

7、括三個整數(shù)，M，N和K，用空格隔開；表示花生田的大小為M*N（1<=M，N<=20），多多采花生的限定時間為K（0<=K<=1000）個單位時間.接下來的M行,每行包括N個非負整數(shù),也用空格隔開;第i+1行的第j個整數(shù)Pij(0<=Pij<=500)表示花生田里植株(i,j)下花生的數(shù)目,0表示該植株下沒有花生。輸出文件輸出文件peanuts.out包括一行.這一行只包含一個整數(shù)，即在限定時間內，多多最多可以采到的花生的個數(shù)。樣例輸入6 7 210 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0

8、 0 9 0 0 00 0 0 0 0 0 0樣例輸出137樣例輸入26 7 200 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 0樣例輸出228【源程序清單】PROG: PeanutsLANG: PASCALID: xyj-flashProgram Peanuts;VarX,Y,Value:Array0.400 of Longint;Map:Array1.20,1.20 of Longint;M,N,K,I,J,Top,T,Sum:Longint;Procedure Sort(L,R

9、:Longint);VarI,J,Mid:Longint;BeginI:=L;J:=R;Mid:=Value(L+R) Div 2;RepeatWhile ValueI>Mid do Inc(I);While ValueJ<Mid do Dec(J);If I<=J Then BeginValue0:=ValueI;ValueI:=ValueJ;ValueJ:=Value0;X0:=XI;XI:=XJ;XJ:=X0;Y0:=YI;YI:=YJ;YJ:=Y0;Inc(I);Dec(J);End;Until I>J;If I<R Then Sort(I,R);If L<J Then Sort(L,J);End;Procedure Print(K:Longint);BeginWriteln(K);Halt;End;BeginRead(M,N,K);Top:=0;For I:=1 to M do For J:=1 to N do BeginRead(MapI,J);If MapI,J<>0 Then BeginInc(Top);ValueTop:=MapI,J;XTop:=I;YTop:=J;End;End;Sort(1,Top);K:=K-2;X0:=1