小明這天在參加公司團(tuán)建,團(tuán)建項(xiàng)目是爬山。在 x 軸上從左到右一共有 n座山,第 i 座山的高度為 hi。他們需要從左到右依次爬過(guò)所有的山,需要花費(fèi)的體力值為 S = Σni=1hi。
然而小明偷偷學(xué)了魔法,可以降低一些山的高度。他掌握兩種魔法,第一種魔法可以將高度為 H 的山的高度變?yōu)??√H?,可以使用 P 次;第二種魔法可以將高度為 H 的山的高度變?yōu)??H/2?,可以使用 Q 次。并且對(duì)于每座山可以按任意順序多次釋放這兩種魔法。
小明想合理規(guī)劃在哪些山使用魔法,使得爬山花費(fèi)的體力值最少。請(qǐng)問(wèn)最優(yōu)情況下需要花費(fèi)的體力值是多少?
輸入共兩行。
第一行為三個(gè)整數(shù) n,P,Q。
第二行為 n 個(gè)整數(shù) h1,h2,. . . ,hn。
4 1 1 4 5 6 49
18
【樣例說(shuō)明】將第四座山變?yōu)??√49? = 7,然后再將第四座山變?yōu)??7/2? = 3。體力值為 4 + 5 + 6 + 3 = 18。
【評(píng)測(cè)用例規(guī)模與約定】
對(duì)于 20% 的評(píng)測(cè)用例,保證 n ≤ 8,P = 0。
對(duì)于 100% 的評(píng)測(cè)用例,保證 n ≤ 100000,0 ≤ P ≤ n,0 ≤ Q ≤ n,0 ≤ hi ≤ 100000。
2024年第十五屆藍(lán)橋杯第一次比賽真題,。。。。。。。。。。。。
參加下周比賽的同學(xué)可以做一下,體會(huì)一下類型和難度