[計算機]花生采摘解題報告-wenkub
2023-04-07 02:14:42 本頁面
【正文】 時間復雜度就上升到了，因為除了少部分特殊的排序之外，因此不可避免地導致了的排序復雜度?！拘牡皿w會】花生采摘是一道典型的貪心問題，也是一道典型的簡單題（因此這道題的算法分析也只能這樣簡單了……）。因此，我們先對數(shù)據(jù)進行從大到小的排序，然后每次都取其中的最大值?！痘ㄉ烧方忸}報告By sx349 【摘要】核心算法思想：貪心主要數(shù)據(jù)結(jié)構(gòu)：其他輔助知識：時間復雜度：空間復雜度：【題目大意】給定一個非空矩陣，每次都從中選擇一個最大值并將其從矩陣中排除，將這些取出的數(shù)排序后計算其花費（相鄰兩數(shù)的花費是其在矩陣之間的曼哈頓距離），求在給定最大花費下，能取到的最大值的最大總和。因為必須在規(guī)定的時間內(nèi)回到路邊，所以在每次取最大值時，首先判斷在采摘了這一次之后是否有足夠的時間回到路邊，即(去采摘目標花生的時間)+(采摘那目標花生所用的1單位時間)+(從目標所在地往第一行的時間)=(剩下的單位時間)。但是這道題有一個區(qū)別于其他問題的地方：在解決問題的過程中，主要部分（連續(xù)取最大值）的時間復雜度只需要，而排序卻花費了的時間復雜度。如此一來，就超過了順序查找的復雜度了。如果這個問題的輸入達到了上千萬乃至上億，單單讀入的復雜度就已經(jīng)使程序罷工了。這天，他們兩個正沿著鄉(xiāng)間小路散步，突然發(fā)現(xiàn)路邊的告示牌上貼著一張小小的紙條：“歡迎免費品嘗我種的花生！——熊字”。為了訓練多多的算術(shù)，魯濱遜先生說：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此類推，不過你一定要在我限定的時間內(nèi)回到路邊。沿著圖示的路線，多多在21個單位時間內(nèi)，最多可以采到3
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1