分蛋糕
2023-07-05 20:55 作者:AK全場(chǎng) | 我要投稿
題目傳送門(http://www.temege.com/p/1885?tid=6270d31ad052d378b8a9718d)
題目描述：
有一個(gè) n 邊形的蛋糕，依次按順時(shí)針的方向?qū)Ω鱾€(gè)頂點(diǎn)進(jìn)行標(biāo)號(hào)（1,1,2,2,…，n），現(xiàn)在要將蛋糕切成 n-2 份（每切一次都必須從頂點(diǎn)開(kāi)始到另一個(gè)頂點(diǎn)結(jié)束）。第 i 份蛋糕 ai 代表第 i 份蛋糕的頂點(diǎn)乘積。怎樣切蛋糕，才能使
?值最小呢？
解題思路：
根據(jù)貪心的思想，我們每次應(yīng)該盡可能選擇較小的頂點(diǎn)來(lái)進(jìn)行分割。
因此，我們可以把問(wèn)題轉(zhuǎn)化為：找到一個(gè)合適的起點(diǎn)，使得分割線不斷向它所連接的頂點(diǎn)中編號(hào)更小的那個(gè)移動(dòng)，直到遇到首尾相接的情況為止。
在這個(gè)過(guò)程中，我們需要維護(hù)當(dāng)前已經(jīng)切了多少段、以及當(dāng)前的乘積之和。如果當(dāng)前已經(jīng)切割了 n-2 段，那么就更新答案并退出循環(huán)。
標(biāo)簽：
