欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

贪心策略摘果子(洛谷P1478题题解,Java语言描述)

程序员文章站 2022-07-13 13:53:02
...

题目要求

P1478题目链接

贪心策略摘果子(洛谷P1478题题解,Java语言描述)
贪心策略摘果子(洛谷P1478题题解,Java语言描述)

分析

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

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

建议大家移步这里 → 精辟题解
这位爷写了本题的暴力搜索、剪枝搜索、记忆化搜索、动态规划(背包)、贪心的各种详解,可以说对初学者来说很好啦。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);
    }
}