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