贪心法入门

算法简介

   所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
   贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
  所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

题目链接

SGU-548 Dragons and Princesses

题意

一个经典的以龙-骑士-公主的为背景的题目：
有n（2e5数量级）个格子排成一行，第一个格子里只有骑士，最后一个格子里只有目标公主，其它格子里有龙或其它公主，每个公主有对应的一个漂亮值，每条龙对应一个财富值，骑士从第一个格子出发，一直走到最后一个格子救出目标公主，有两点需要注意：

1. 如果格子里是龙，那么骑士可以选择杀死或者不杀死龙，如果杀死，可以得到这条龙的财富值；
2. 如果格子里是公主（无论是不是目标公主），只要骑士当前杀死的龙的数量>=当前公主的漂亮值，就可以娶她，而且必须娶，然后结束行程；
   问骑士是否能娶到目标公主，如果能，求出能积累的最大的财富值，并给出方案。

解法

这题可以用贪心法来做：

1. 在遇到龙时，我们先假设将它们都标记成要杀死；
2. 在遇到[2,n-1]中的公主时，如果当前标记成要杀死的龙数量太多了，那我们肯定想办法挑出几条已经标记成杀死的龙，标记成不杀。那么怎么挑选呢？显然要选取其中财富值最小的那几条；

这样做的原因如下：
每条龙有两个属性：财富值、对骑士所杀的龙的数量的贡献值；每条龙的贡献值都是1，而目标是要让财富值尽量多，所以，要放弃杀死相同数量的龙的前提下，肯定会选择放弃财富值小的；
如何在当前标记成要杀死的龙中找出财富值最小的呢？这时候就可以借助堆（大部分操作复杂度都是lgn）了,这里要注意的是，c++里的priority_queue默认是最大堆，而java里的PriorityQueue默认是最小堆，所以在重载<号或者实现Comparable方法的时候要注意不要弄反了。

核心代码

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;
        }
    }
}

完整代码