如何用贪心算法与最大堆高效解决工厂污染减半问题-java教程-PHP中文网

如何用贪心算法与最大堆高效解决工厂污染减半问题

本文介绍一种基于最大堆的贪心策略，用于求解“最少安装多少个滤网才能使总污染量减半”的经典面试题，时间复杂度优化至 o(k log n)，适用于大规模数据（n ≤ 30,000）。

本文介绍一种基于最大堆的贪心策略，用于求解“最少安装多少个滤网才能使总污染量减半”的经典面试题，时间复杂度优化至 o(k log n)，适用于大规模数据（n ≤ 30,000）。

在工业环保类算法题中，一个常见且极具启发性的场景是：多个工厂排放不同量的污染气体，每个滤网可将单个工厂的当前污染值减半（支持多次安装，每次对当前值再减半），目标是使所有工厂污染总和 ≤ 初始总和的一半，并求所需滤网的最小数量。

直观来看，为最大化单次滤网的减排效果，应始终优先处理当前污染值最高的工厂——因为减半操作带来的绝对减少量（即 current_value / 2）越大，越能快速逼近目标。这正是贪心策略的核心思想：每一步选择局部最优（削减最多），最终达成全局最优（总滤网数最少）。

但难点在于：工厂污染值会动态变化（如 18 → 9 → 4.5 → 2.25…），我们需要持续、高效地获取当前最大值，并插入其减半后的新值。普通数组排序（O(n log n) 每轮）不可行；而最大堆（Max-Heap） 正是为此设计的数据结构：插入和弹出最大值均为 O(log n)，完美匹配该动态最值需求。

Java 中可通过 PriorityQueue 配合 Collections.reverseOrder() 构建最大堆。算法流程如下：

DreamStudio

一款基于Stable Diffusion生态的在线AI图像生成工具，帮助用户通过文字描述创建艺术图像和视觉素材。

下载

计算初始总污染 currentPollution 和目标值 targetPollution = currentPollution / 2.0；
将所有污染值入堆；
当 currentPollution > targetPollution 时循环：
- 弹出最大值 maxPollution；
- 计算其减半值 pollutionAfterFilter = maxPollution / 2.0；
- 将该减半值重新入堆；
- 更新总污染：currentPollution -= pollutionAfterFilter（等价于 currentPollution = currentPollution - maxPollution + pollutionAfterFilter）；
- 滤网计数 numFilters++；
返回 numFilters。

以下是完整、可直接运行的 Java 实现：

import java.util.*;

public class PollutionFilter {
    public static int getMinimumFilters(double[] pollutionLevels) {
        double currentPollution = Arrays.stream(pollutionLevels).sum();
        double targetPollution = currentPollution / 2.0;

        // 构建最大堆
        PriorityQueue<double> maxHeap = new PriorityQueue(Collections.reverseOrder());
        for (double level : pollutionLevels) {
            maxHeap.offer(level);
        }

        int numFilters = 0;
        while (currentPollution > targetPollution) {
            double maxPollution = maxHeap.poll(); 
            double reduced = maxPollution / 2.0;
            maxHeap.offer(reduced); 
            currentPollution -= reduced; // 减去新增的“减少量”
            numFilters++;
        }
        return numFilters;
    }

    public static void main(String[] args) {
        double[] pollutionLevels = {3, 5, 6, 1, 18};
        System.out.println("Minimum number of filters needed: " + getMinimumFilters(pollutionLevels));
        // 输出：3
    }
}</double>

⚠️ 关键注意事项：