算法簡(jiǎn)介
所謂貪心算法是指轧房，在對(duì)問(wèn)題求解時(shí)究西，總是做出在當(dāng)前看來(lái)是最好的選擇媒怯。也就是說(shuō)边酒，不從整體最優(yōu)上加以考慮僚碎，他所做出的僅是在某種意義上的局部最優(yōu)解揽涮。
貪心算法沒(méi)有固定的算法框架抠藕，算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇。必須注意的是蒋困，貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解盾似，選擇的貪心策略必須具備無(wú)后效性，即某個(gè)狀態(tài)以后的過(guò)程不會(huì)影響以前的狀態(tài)雪标，只與當(dāng)前狀態(tài)有關(guān)零院。
所以對(duì)所采用的貪心策略一定要仔細(xì)分析其是否滿足無(wú)后效性。
題目鏈接
SGU-548 Dragons and Princesses
題意
一個(gè)經(jīng)典的以龍-騎士-公主的為背景的題目：
有n（2e5數(shù)量級(jí)）個(gè)格子排成一行村刨，第一個(gè)格子里只有騎士告抄，最后一個(gè)格子里只有目標(biāo)公主，其它格子里有龍或其它公主嵌牺，每個(gè)公主有對(duì)應(yīng)的一個(gè)漂亮值打洼，每條龍對(duì)應(yīng)一個(gè)財(cái)富值龄糊，騎士從第一個(gè)格子出發(fā)，一直走到最后一個(gè)格子救出目標(biāo)公主募疮，有兩點(diǎn)需要注意：
- 如果格子里是龍炫惩，那么騎士可以選擇殺死或者不殺死龍，如果殺死阿浓，可以得到這條龍的財(cái)富值他嚷；
- 如果格子里是公主（無(wú)論是不是目標(biāo)公主），只要騎士當(dāng)前殺死的龍的數(shù)量>=當(dāng)前公主的漂亮值搔扁，就可以娶她爸舒，而且必須娶，然后結(jié)束行程稿蹲；
問(wèn)騎士是否能娶到目標(biāo)公主扭勉，如果能，求出能積累的最大的財(cái)富值苛聘，并給出方案涂炎。
解法
這題可以用貪心法來(lái)做：
- 在遇到龍時(shí)，我們先假設(shè)將它們都標(biāo)記成要?dú)⑺溃?/li>
- 在遇到[2,n-1]中的公主時(shí)设哗，如果當(dāng)前標(biāo)記成要?dú)⑺赖凝垟?shù)量太多了唱捣，那我們肯定想辦法挑出幾條已經(jīng)標(biāo)記成殺死的龍，標(biāo)記成不殺网梢。那么怎么挑選呢震缭？顯然要選取其中財(cái)富值最小的那幾條；
這樣做的原因如下：
每條龍有兩個(gè)屬性：財(cái)富值战虏、對(duì)騎士所殺的龍的數(shù)量的貢獻(xiàn)值拣宰；每條龍的貢獻(xiàn)值都是1，而目標(biāo)是要讓財(cái)富值盡量多烦感，所以巡社，要放棄殺死相同數(shù)量的龍的前提下，肯定會(huì)選擇放棄財(cái)富值小的手趣；
如何在當(dāng)前標(biāo)記成要?dú)⑺赖凝堉姓页鲐?cái)富值最小的呢晌该？這時(shí)候就可以借助堆（大部分操作復(fù)雜度都是lgn）了,這里要注意的是，c++里的priority_queue默認(rèn)是最大堆绿渣，而java里的PriorityQueue默認(rèn)是最小堆朝群，所以在重載<號(hào)或者實(shí)現(xiàn)Comparable方法的時(shí)候要注意不要弄反了。
核心代碼
for (int i = 2; i <= n; ++i) {
String cmd = in.next();
int curCoins = in.nextInt();
if (cmd.equals("d")) {
dragons.add(new Dragon(i, curCoins));
coinsGet += curCoins;
} else {
if (i < n) {
while (!dragons.isEmpty() && dragons.size() >= curCoins) {
Dragon dragon = dragons.poll();
coinsGet -= dragon.getCoins();
}
} else {
getLastPrincess = dragons.size() >= curCoins;
}
}
}
