http://acm.cist.bnu.edu.cn/contest/problem_show.php?pid=1069給一些物品,虛擬幣價(jià)格v[i]=2^(ki-1),實(shí)際價(jià)值w[i].現(xiàn)給S個(gè)虛擬幣.要求把這些虛擬幣恰好花完,并且購得物品的實(shí)際價(jià)值總和最大.
顯然,可行的購買方案必能將所購物品分成若干組,其中每組的總價(jià)格為2^(pi-1),其中pi為S的二進(jìn)制表示為1的所有位.
因此可以按位貪心,從S的最低位開始.設(shè)當(dāng)前處理第k位:
1.選取剩余物品價(jià)格為2^(k-1)中價(jià)值最大的那個(gè),如果沒有價(jià)格為2^(k-1)的物品,則表示任務(wù)無法達(dá)成.
2.將其它價(jià)格為2^(k-1)的物品,按價(jià)值從大到小排序,相鄰兩個(gè)合并成價(jià)格為2^k的物品,累積到下一階段.
這里挖掘出的貪心性質(zhì)為: 一個(gè)數(shù)第k位的1,只能由不高于第k位的1合成得到.
posted on 2009-04-25 11:44
wolf5x 閱讀(222)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
acm_icpc