NekoNowcoder

Appearance

Governing sand - 题解 ​

标签与难度 ​

标签: 贪心, 排序, 枚举, 桶排序思想, 前缀和思想 难度: 1700

题目大意喵~ ​

主人你好呀~ 这道题是说，有一个被风沙困扰的Wowo村，村前有一片森林可以防沙。但这片森林要想起作用，必须满足一个奇特的条件：森林里最高的树的数量必须严格大于森林里所有树总数的一半，喵~

我们可以花钱砍掉一些树来满足这个条件。现在有 n 种树，每种树都有自己的高度 H、砍伐单价 C 和数量 P。我们的任务就是，用最少的钱来改造森林，让它达到防沙的要求。

输入会给出 n，以及接下来 n 行，每行是 H_i, C_i, P_i。我们要输出一个数字，就是最少的总花费，呐。

解题思路分析 ​

这道题的目标是求最小花费，通常会和动态规划或者贪心有关，喵~ 让我们先来分析一下这个奇怪的防沙条件。

假设我们改造完森林后，最高的树的高度是 H_max，这种高度的树有 N_tallest 棵，而森林里剩下的其他树（高度小于 H_max）一共有 N_other 棵。那么，此时森林的总树木数量就是 N_total = N_tallest + N_other。

题目要求是 N_tallest > N_total / 2。我们来把这个式子变个形，看看能不能发现什么小秘密~ N_tallest > (N_tallest + N_other) / 2 两边都乘以2，得到： 2 * N_tallest > N_tallest + N_other 再把一个 N_tallest 移到右边： N_tallest > N_other

哇！原来这个复杂的条件，本质上就是说最高树的数量必须比其他所有树加起来还要多！只要满足这个，就大功告成啦，的说。

那么，最终森林里最高的树是哪一种呢？我们并不知道。但是，最终的最高高度 H_max 一定是原来存在的某一种树的高度 H_i。为什么呢？因为我们只能砍树，不能把树变高。如果我们选择一个不存在的高度作为 H_max，那最高的树就是空的，数量为0，肯定不行呀。

所以，一个很自然的想法就诞生了：我们可以枚举最终保留的最高树的高度 H_target 是多少。对于每一种可能的 H_target，我们都计算出达成目标的最小花费，然后取所有这些花费中的最小值，就是最终答案啦！

好，现在我们来固定一个目标高度 H_target，看看需要做什么：

  1. 强制砍伐：所有高度大于 H_target 的树都必须被砍掉，不然 H_target 就不是最高高度了。这部分的开销是固定的，我们必须支付。

  2. 确定主要群体：所有高度等于 H_target 的树，就成了我们新的“最高树天团”，我们把它们的总数记为 N_tallest。

  3. 确定其他群体：所有高度小于 H_target 的树，就是“其他树”，总数记为 N_other。

  4. 判断与调整：现在我们来检查 N_tallest > N_other 是否成立。

    • 如果已经成立了，太棒了！我们只需要支付第一步的强制砍伐费用。
    • 如果不成立，即 N_tallest <= N_other，我们就必须继续砍树。为了尽快满足 N_tallest > N_other，我们应该从 N_other 这个群体里砍树。因为如果砍 N_tallest 里的树，会让 N_tallest 变少，离目标更远了，不划算喵~
    • 我们需要砍掉多少棵呢？为了让 N_other 变得比 N_tallest 小，最少要让 N_other 减小到 N_tallest - 1。所以，需要砍掉的树的数量是 N_other - (N_tallest - 1) 棵。
    • 砍哪些呢？当然是砍 N_other 群体里最便宜的那些树啦！这是一个非常经典的贪心策略。

把上面的思路整理一下，一个高效的算法就出现啦：

  1. 首先，把所有种类的树按照高度从高到低排序。这样方便我们从最高的树开始枚举。
  2. 我们用一个循环，从最高的树种开始，依次考虑每一种高度作为 H_target。
  3. 为了快速找到需要砍的 k 棵最便宜的树，我们可以用一个频率数组（桶） cost_counts 来记录当前可砍的“其他树”里，各种费用的树分别有多少棵。因为费用 C 的范围很小（1到200），用桶来统计再合适不过了！
  4. 我们从高到低遍历所有不同的高度。假设当前处理的高度是 H_curr：
    • 所有比 H_curr 更高的树，都已经被我们“处理”过了，它们要么被强制砍伐，要么在之前的步骤里被当成过 H_target。我们可以维护一个变量 cost_of_mandatory_cuts 来记录砍掉所有高于 H_curr 的树的总费用。
    • 所有高度等于 H_curr 的树，组成了我们的 N_tallest。
    • 所有高度小于 H_curr 的树，组成了我们的 N_other。它们的费用分布就存在我们的 cost_counts 桶里。
    • 我们计算需要从 N_other 中砍掉 k = N_other - (N_tallest - 1) 棵树。
    • 然后利用 cost_counts 桶，从费用1开始，贪心地砍掉 k 棵最便宜的树，计算出这部分的 optional_cut_cost。
    • 当前 H_curr 作为最高高度的总费用就是 cost_of_mandatory_cuts + optional_cut_cost。用它来更新我们的全局最小答案。
    • 处理完 H_curr 后，我们要把它也加入到“必须砍掉”的行列中，为下一个更低的高度做准备。也就是把砍掉 H_curr 这批树的费用加到 cost_of_mandatory_cuts 里，并更新 cost_counts 桶。

通过这样一次遍历，我们就能找到全局最优解了，喵~ 这个方法把枚举、排序和贪心完美地结合在了一起！

代码实现 ​

这是我根据上面的思路，精心重构的一份代码哦~ 希望能帮到你，喵~

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

// 使用 long long 防止费用和数量相乘后溢出
using int64 = long long;

// 定义一个结构体来存放每种树的信息，方便管理
struct TreeInfo {
    int64 h, c, p;
};

// 排序时使用，按高度从高到低排序
bool compareTrees(const TreeInfo& a, const TreeInfo& b) {
    return a.h > b.h;
}

void solve() {
    int n;
    if (!(std::cin >> n)) {
        return;
    }

    std::vector<TreeInfo> trees(n);
    int64 total_tree_count = 0;
    // 费用的范围是1-200，所以开201大小的桶就够啦
    std::vector<int64> cost_counts(201, 0);

    for (int i = 0; i < n; ++i) {
        std::cin >> trees[i].h >> trees[i].c >> trees[i].p;
        total_tree_count += trees[i].p;
        cost_counts[trees[i].c] += trees[i].p;
    }

    // 按高度从高到低排序
    std::sort(trees.begin(), trees.end(), compareTrees);

    int64 min_total_cost = -1; // 初始化为-1，或者一个非常大的数
    int64 cost_of_mandatory_cuts = 0; // 记录强制砍伐的费用

    int i = 0;
    while (i < n) {
        // --- Step 1: 将同高度的树作为一组进行处理 ---
        int j = i;
        while (j < n && trees[j].h == trees[i].h) {
            j++;
        }
        // 现在 [i, j-1] 区间内的树高度都相同
        
        int64 num_as_tallest = 0; // 当前高度的树的总数
        int64 cost_of_this_block = 0; // 当前高度这批树的总价值
        for (int k = i; k < j; ++k) {
            num_as_tallest += trees[k].p;
            cost_of_this_block += trees[k].p * trees[k].c;
            // 从桶中移除当前高度的树，因为它们不是“其他树”
            cost_counts[trees[k].c] -= trees[k].p;
        }

        // --- Step 2: 计算需要额外砍伐的树木数量 ---
        int64 num_other = total_tree_count - num_as_tallest;
        int64 num_to_cut = 0;
        if (num_as_tallest <= num_other) {
            num_to_cut = num_other - (num_as_tallest - 1);
        }

        // --- Step 3: 贪心计算额外砍伐的费用 ---
        int64 optional_cut_cost = 0;
        int64 remaining_to_cut = num_to_cut;
        if (remaining_to_cut > 0) {
            // 从费用最低的桶开始，贪心砍树
            for (int cost = 1; cost <= 200; ++cost) {
                if (cost_counts[cost] > 0) {
                    int64 can_cut = std::min(remaining_to_cut, cost_counts[cost]);
                    optional_cut_cost += can_cut * cost;
                    remaining_to_cut -= can_cut;
                    if (remaining_to_cut == 0) {
                        break;
                    }
                }
            }
        }
        
        // --- Step 4: 更新全局最小费用 ---
        int64 current_total_cost = cost_of_mandatory_cuts + optional_cut_cost;
        if (min_total_cost == -1 || current_total_cost < min_total_cost) {
            min_total_cost = current_total_cost;
        }

        // --- Step 5: 准备下一轮迭代 ---
        // 当前这批树在下一轮中将成为“高于目标高度”的树，所以计入强制砍伐成本
        cost_of_mandatory_cuts += cost_of_this_block;
        // 更新森林中剩余的树木总数
        total_tree_count -= num_as_tallest;

        // 跳到下一个不同高度的树
        i = j;
    }

    std::cout << min_total_cost << std::endl;
}

int main() {
    // 提高cin/cout效率
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    // 题目是多组输入
    while (std::cin.peek() != EOF && std::cin.peek() != '\n') {
        solve();
    }
    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(Nlog⁡N+N×Cmax)O(N \log N + N \times C_{max})

    • 首先，我们需要对 N 种树按高度进行排序，这部分的时间复杂度是 O(Nlog⁡N)O(N \log N)，呐。
    • 接着，我们遍历排序后的树种。虽然是 while 循环，但每个树种只会被访问一次。在循环内部，最耗时的操作是计算 optional_cut_cost，这需要遍历费用桶，最多遍历 C_{max}（这里是200）次。
    • 所以，总的时间复杂度是排序加上遍历，即 O(Nlog⁡N+N×Cmax)O(N \log N + N \times C_{max})。因为 C_{max} 是个不大的常数，所以复杂度近似于 O(Nlog⁡N)O(N \log N)。

  • 空间复杂度: O(N+Cmax)O(N + C_{max})

    • 我们需要一个 vector 来存储 N 种树的信息，空间是 O(N)O(N)。
    • 我们还需要一个频率数组（桶）来统计不同费用的树的数量，其大小为 C_{max} + 1，所以是 O(Cmax)O(C_{max})。
    • 合计起来，总的空间复杂度就是 O(N+Cmax)O(N + C_{max})，喵~

知识点总结 ​

这道题真是一次愉快的思维体操呢！我们主要用到了以下几个知识点：

  1. 问题转化: 将复杂的 N_tallest > N_total / 2 条件转化为更直观的 N_tallest > N_other，是解题的关键第一步。
  2. 枚举思想: 当无法直接确定最优解的某个属性时（比如本题的最终最高高度），可以尝试枚举所有可能性，对每种可能性计算一个结果，最后取最优。
  3. 贪心算法: 在需要做出系列选择以达到最优时，如果每一步都采取当前看起来最好的选择，最终能得到全局最优解，这就是贪心。本题中“砍掉最便宜的树”就是典型的贪心策略。
  4. 排序: 排序是很多算法的预处理步骤。本题通过按高度排序，使得我们可以有序地、不重不漏地枚举所有情况，并高效地维护状态。
  5. 桶/频率数组: 对于值域范围不大的数据（如本题的费用 C），使用桶来计数是一种非常高效的技巧，可以让我们在 O(1)O(1) 的时间内访问特定值的数据，或者像本题一样快速找到最小/最大的元素。

希望这篇题解能对你有所帮助，如果还有不明白的地方，随时可以再来问我哦，喵~