[計算機]花生采摘解題報告(已修改)
2025-04-04 02:14 本頁面
【正文】 《花生采摘》解題報告By sx349 【摘要】核心算法思想：貪心主要數(shù)據(jù)結(jié)構(gòu)：其他輔助知識：時間復雜度：空間復雜度：【題目大意】給定一個非空矩陣，每次都從中選擇一個最大值并將其從矩陣中排除，將這些取出的數(shù)排序后計算其花費（相鄰兩數(shù)的花費是其在矩陣之間的曼哈頓距離），求在給定最大花費下，能取到的最大值的最大總和?！舅惴ǚ治觥课闹姓f道：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此類推，不過你一定要在我限定的時間內(nèi)回到路邊?！备鶕?jù)這一句話，我們直接就可以得出，這道題應該采用貪心的算法。因此，我們先對數(shù)據(jù)進行從大到小的排序，然后每次都取其中的最大值。因為必須在規(guī)定的時間內(nèi)回到路邊，所以在每次取最大值時，首先判斷在采摘了這一次之后是否有足夠的時間回到路邊，即(去采摘目標花生的時間)+(采摘那目標花生所用的1單位時間)+(從目標所在地往第一行的時間)=(剩下的單位時間)。若條件不滿足就停止，若滿足就繼續(xù)采摘。由于去摘花生必須從路邊進入花生田和從花生田出來，所以我們可以先減去2個單位時間，再將剩下的時間進行模擬。【心得體會】花生采摘是一道典型的貪心問題，也是一道典型的簡單題（因此這道題的算法分析也只能這樣簡單了……）。但是這道題有一個區(qū)別于其他問題的地方：在解決問題的過程中，主要部分（連續(xù)取最大值）的時間復雜度只需要，而排序卻花費了的時間復雜度。這一點確實是在許多情況下無法回避的一個問題。我一直記得我們平時上課的計算機書上有一個簡單的例子：給你一些電話號碼，讓你去尋找某一個指定的號碼。書上的解釋是用二分
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1