贪心策略摘果子（洛谷P1478题题解，Java语言描述）

题目要求

P1478题目链接

分析

本题的低配版题目链接 → 题解

那个题就是纯水题没啥可写的，我除了贴代码无话可说，但这题吧，虽然不算难，但也可一说。

建议大家移步这里 → 精辟题解
这位爷写了本题的暴力搜索、剪枝搜索、记忆化搜索、动态规划（背包）、贪心的各种详解，可以说对初学者来说很好啦。OrzOrzOrz……

显然，本题既然可用贪心，贪心就是最快方案啦，我们只需要每次取最省力（最小代价）的一个果子，即可更快得到最优解。
贪心，妙不可言~~

顺便简单提一提贪心：
贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

之前我也简单的提过贪心，贪心往往能取得更高的效率，但适用范围不是那么广泛，需要我们认真思考什么时候适合用什么时候不能用。当然，本题作为洛谷橙题，读罢题意，贪心足矣……

请看我AC代码吧！

AC代码（Java语言描述）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt(), strength = scanner.nextInt(), maxHeight = scanner.nextInt()+scanner.nextInt();
        int[] array = new int[101];
        for (int i = 0; i < num; i++) {
            int tempHeight = scanner.nextInt(), needStrength = scanner.nextInt();
            if (tempHeight <= maxHeight) {
                array[needStrength]++;
            }
        }
        scanner.close();
        int counter = 0, sum = 0;
        outer:
        for (int i = 0; i <= 100; i++) {
            while (array[i] > 0) {
                sum += i;
                if (sum <= strength) {
                    counter++;
                    array[i]--;
                } else {
                    break outer;
                }
            }
        }
        System.out.println(counter);
    }
}