求减半区域总污染所需的最少过滤器数量（Visa面试题）

问题描述 #

某区域内的工厂会产生污染气体，需在各工厂安装过滤器以减少污染。每安装一个过滤器，该工厂的污染量将减半，每个工厂可安装多个过滤器。给定一个包含N个整数的列表，代表N个工厂的污染水平，请计算将区域总污染量减半所需的最少过滤器数量。

示例 #

假设污染水平列表为[3, 5, 6, 1, 18]：

• 总污染量 = 3+5+6+1+18 = 33，目标值为 33/2 = 16.5
• 在污染值18的工厂安装1个过滤器 → 污染变为[3,5,6,1,9]，总污染24
• 再次在该工厂安装1个过滤器 → 污染变为[3,5,6,1,4.5]，总污染19.5
• 在污染值6的工厂安装1个过滤器 → 污染变为[3,5,3,1,4.5]，总污染16.5
  共需3个过滤器，为最少数量。

约束条件 #

• N的取值范围为[1, 30000]
• 列表中每个元素的取值范围为[0, 70000]

我的错误尝试代码 #

import java.util.Arrays;

public class FilterCalculator {
    public static int getMinimumFilters(double[] pollutionLevels) {
        double totalPollution = Arrays.stream(pollutionLevels).sum();
        double targetPollution = totalPollution / 2.0;
        int numFilters = 0;
        double currentPollution = 0;
        double tempPollution = 0;

        Arrays.sort(pollutionLevels);

        for (double i = pollutionLevels.length -1; i >= 0; i--) {
            currentPollution = (totalPollution - pollutionLevels[(int) i]) + pollutionLevels[(int) i]/2;
            numFilters++;
            if (currentPollution <= targetPollution) {
                break;
            }

        }

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

我的思路 #

计算数组总和，利用总和与目标污染值的差值，判断哪些工厂的污染量需要减半以达成目标，但不知道具体怎么实现最优选择。

问题分析与正确解法 #

你的错误代码核心问题是：仅对每个工厂最多处理一次，但实际上单个工厂可能需要多次安装过滤器（比如示例中的18需要两次），排序后单次处理无法覆盖这种情况。

要得到最少过滤器数量，每次必须选择当前污染最大的工厂安装过滤器——因为这样每次能减少最多的污染量，最快达到目标值。这种场景适合用**大顶堆（优先队列）**来实现，因为堆能高效地获取当前最大值，处理后再放回堆中循环操作。

正确代码实现 #

import java.util.PriorityQueue;
import java.util.Collections;

public class PollutionFilter {
    public static int getMinimumFilters(int[] pollutionLevels) {
        // 计算总污染量
        long totalPollution = 0;
        // 初始化大顶堆，优先队列默认是小顶堆，需反转排序器
        PriorityQueue<Long> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int level : pollutionLevels) {
            if (level > 0) { // 跳过污染为0的工厂，无需处理
                maxHeap.add((long) level);
                totalPollution += level;
            }
        }
        
        if (totalPollution == 0) {
            return 0; // 没有污染，不需要过滤器
        }
        
        long targetPollution = totalPollution / 2;
        int filterCount = 0;
        
        while (totalPollution > targetPollution) {
            // 取出当前污染最大的工厂值
            long currentMax = maxHeap.poll();
            // 计算减半后的值
            long halved = currentMax / 2;
            // 更新总污染量
            totalPollution -= (currentMax - halved);
            filterCount++;
            // 把减半后的值放回堆中，后续可能还需要处理
            maxHeap.add(halved);
        }
        
        return filterCount;
    }

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

代码说明 #

1. 大顶堆的使用：确保每次快速获取当前污染最大的工厂，保证每次操作减少的污染量最多，从而用最少过滤器达到目标。
2. 0值处理：污染为0的工厂无需安装过滤器，直接跳过。
3. 循环逻辑：每次取出最大值，减半后放回堆，同时更新总污染量，直到总污染量小于等于目标值。
4. 整数类型优化：用long类型计算避免浮点数精度问题，单个元素最大70000，30000个元素总和为2.1e9，long完全可以容纳。

内容的提问来源于stack exchange，提问作者codeskin