神农尝百草 - Java 代码实现及优化 - 常规

神农尝百草 - Java 代码实现及优化

传说神农为了拯救黎民苍生尝遍草药无数。现在神农收集了 n 株不同种类的草药，编号依次为 1～n。为了了解草药的药理，他不得不亲自尝试。每株草药都有其对应的功效 a_i (-10⁹ ≤ a_i ≤ 10⁹)，功效为负时，草药呈现毒性。起初，神农的精力值为 0，每品一株草药，神农的精力值会受草药的功效影响而增加草药对应的功效值（可能加上一个负值），但神农的精力一旦小于 0，他会因为中毒严重而休克。现在，神农从 1～n 依次有选择性地品尝各株草药（对于某株草药，神农选择品尝或者不品尝），问：在神农不休克的前提下，最多可以品尝多少株草药？

输入格式:

第一行输入一个正整数 n (0 ≤ n ≤ 2 × 10⁵)，代表草药的总数。

第二行输入 n 个以空格隔开的整数，第 i 个整数 a_i 代表第 i 株草药的功效。

输出格式:

在一行中输出一个整数，表示神农可以品尝草药的最大数目。

输入样例:

6
4 -4 1 -3 1 -3

输出样例:

样例解释：

神农可以最多品尝 5 株草药（编号：1，3，4，5，6）。

思路：贪心 + 前缀和

首先对草药的功效进行排序（从小到大），这样可以任意选择草药，不会出现奇怪的情况。对于每种草药，都可以选择或不选择，因此可以考虑贪心，每次选择对精力值增加最多的草药，直到精力值为负数，停止选草药。具体实现时可以先对草药功效数组进行前缀和处理，然后对前缀和数组排序，这样每次选草药时，可以用前缀和数组的二分查找查找增加精力值最多的草药。

时间复杂度：O(nlogn)

Java 代码实现：

import java.util.Arrays;
import java.util.Scanner;

public class ShenNong {  
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        scanner.close();

        // 计算前缀和
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + a[i - 1];
        }

        // 对前缀和数组进行排序
        Arrays.sort(sum);

        // 贪心选择草药
        int count = 0;
        long energy = 0;
        for (int i = n; i >= 0; i--) {
            if (energy + sum[i] >= 0) {
                energy += sum[i];
                count++;
            }
        }

        System.out.println(count);
    }
}

代码说明：

首先使用 Scanner 类读取输入数据，将草药的功效存储在 a 数组中。
计算 a 数组的前缀和，存储在 sum 数组中，方便后续二分查找。
对 sum 数组进行排序，以便使用二分查找来找到对精力值增加最多的草药。
使用一个 count 变量记录可以选择的草药数量，使用 energy 变量记录当前的精力值。
从 sum 数组的末尾开始遍历，每次选择对精力值增加最多的草药，直到精力值为负数，停止选择。

总结：

该代码通过贪心算法和前缀和优化，实现了高效的神农尝百草问题求解。代码易于理解，逻辑清晰，可读性强。