Garbage Classification - 题解

标签与难度

标签: 字符串处理, 模拟, 条件判断, 基础算法, 整数算术难度: 800

题目大意喵~

你好呀，未来的算法大师！这道题是关于垃圾分类的，保护环境，我有责，喵~

题目是这样的：我们有一个废弃物，它由多种成分组成，表示为一个只包含小写字母的字符串 s。每个字母代表一种成分。我们还有一个神奇的字符串 t，它像一本字典，告诉我们从 'a' 到 'z' 这26种成分分别属于哪种垃圾：'h' 代表有害垃圾（harmful），'d' 代表干垃圾（dry），'w' 代表湿垃圾（wet）。

我们的任务就是根据以下规则，判断整个废弃物属于哪一类垃圾：

优先判断有害垃圾：如果废弃物中，有害成分的比例 大于等于 25%，那它就是 Harmful 垃圾。
接着判断可回收物：如果不满足上一条，但有害成分的比例 小于等于 10%，那它就是 Recyclable 垃圾。
最后判断干湿垃圾：如果上面两条都不满足（也就是说有害成分的比例在 10% 和 25% 之间），我们就需要比较干、湿垃圾的数量了：
- 如果干垃圾成分的数量 大于等于 湿垃圾成分数量的 2倍，它就是 Dry 垃圾。
- 否则，就是 Wet 垃圾。

我们需要处理 T 组测试数据，并按格式输出每组的结果，呐。

解题思路分析

这道题其实是一个非常可爱的模拟题，只要我们一步一步跟着规则来，就能轻松解决啦，喵~

第一步：理解成分和类型的对应关系

题目给了我们两个字符串 s 和 t。s 是我们要分析的垃圾，比如 s = "banana"。t 是一个长度为26的字符串，是我们的“成分说明书”。t 的第 i 个字符（从0开始数）对应着字母表中第 i 个小写字母的类型。

举个例子，'a' 是字母表的第0个字母，所以它的类型就是 t[0]。'b' 是第1个，类型是 t[1]，以此类推。对于任意一个小写字母 c，我们都可以通过 c - 'a' 这个小技巧得到它在字母表中的索引，从而在 t 中找到它的类型，也就是 t[c - 'a']。是不是很巧妙呀？

第二步：统计各类成分的数量

知道了如何查找每个成分的类型，我们就可以开始统计啦！我们需要三个计数器，分别记录有害（harmful）、干（dry）和湿（wet）垃圾成分的数量。

我们可以遍历字符串 s 的每一个字符 c：

计算出它的索引 idx = c - 'a'。
查看它的类型 type = t[idx]。
根据 type 的值（是 'h', 'd', 还是 'w'），给对应的计数器加一。

遍历完整个 s 之后，我们就会得到 harmful_count, dry_count, wet_count 三个值啦！

第三步：应用分类规则（避免浮点数的小魔法！）

现在我们有了计数，可以开始应用规则了。规则的顺序非常重要，必须严格按照题目给的 if... else if... else... 逻辑来判断。

规则中提到了百分比，比如 25% 和 10%。在编程中，直接用浮点数做除法可能会因为精度问题而出错，比如 (double)harmful_count / s.length() >= 0.25。虽然在这里可能不会出问题，但养成避免浮点数的好习惯，是成为高手的秘诀之一哦！

我们可以用整数乘法来代替。

“有害成分比例 $\ge 25\%$ ” 也就是 $\frac{\text{harmful\_count}}{\text{total\_len}} \ge \frac{25}{100} = \frac{1}{4}$ 。两边同时乘以 total_len 和 4，就变成了 harmful_count * 4 >= total_len。这样就完全是整数运算啦，又快又准！
同理，“有害成分比例 $\le 10\%$ ” 也就是 $\frac{\text{harmful\_count}}{\text{total\_len}} \le \frac{10}{100} = \frac{1}{10}$ 。两边同时乘以 total_len 和 10，就变成了 harmful_count * 10 <= total_len。

所以，我们的判断逻辑就是：

检查 harmful_count * 4 >= s.length() 是否成立。如果成立，就是 "Harmful"。
如果不成立，再检查 harmful_count * 10 <= s.length() 是否成立。如果成立，就是 "Recyclable"。
如果前两条都不成立，最后我们来比较干湿垃圾：检查 dry_count >= wet_count * 2 是否成立。如果成立，就是 "Dry"，否则就是 "Wet"。

把这些步骤组合起来，就能写出漂亮的代码啦！

代码实现

这是我根据上面的思路，精心为你准备的一份代码~ 每一步都有详细的注释，希望能帮到你，喵！

cpp

#include <iostream>
#include <string>
#include <vector>

// 将单个测试用例的逻辑封装成一个函数，让主函数更整洁喵~
void solve(int case_num) {
    // s: 废弃物的成分字符串
    // t: 成分类型映射字符串 ('a'->t[0], 'b'->t[1], ...)
    std::string s, t;
    std::cin >> s >> t;

    int harmful_count = 0;
    int dry_count = 0;
    int wet_count = 0;
    int total_len = s.length();

    // --- 步骤1 & 2: 遍历s，统计各类成分数量 ---
    // 使用基于范围的for循环，代码更简洁易读呐
    for (char component : s) {
        // 'a'的ASCII码是97, 'b'是98...
        // component - 'a' 可以巧妙地将 'a'...'z' 映射到 0...25
        int index = component - 'a';
        char type = t[index];

        if (type == 'h') {
            harmful_count++;
        } else if (type == 'd') {
            dry_count++;
        } else if (type == 'w') {
        	wet_count++;
        }
    }

    // --- 步骤3: 按照规则顺序进行分类判断 ---
    std::cout << "Case #" << case_num << ": ";

    // 规则1: 有害垃圾比例 >= 25% (1/4)
    // 使用整数乘法避免浮点数精度问题: harmful_count / total_len >= 1/4  =>  harmful_count * 4 >= total_len
    if (harmful_count * 4 >= total_len) {
        std::cout << "Harmful\n";
    } 
    // 规则2: 有害垃圾比例 <= 10% (1/10)
    // 同理: harmful_count / total_len <= 1/10  =>  harmful_count * 10 <= total_len
    else if (harmful_count * 10 <= total_len) {
        std::cout << "Recyclable\n";
    } 
    // 规则3: 其他情况，比较干湿垃圾
    else {
        // 干垃圾数量 >= 2 * 湿垃圾数量
        if (dry_count >= wet_count * 2) {
            std::cout << "Dry\n";
        } else {
            std::cout << "Wet\n";
        }
    }
}

int main() {
    // 加速C++的cin和cout，对付大量输入输出时很有用哦！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T;
    std::cin >> T;
    for (int i = 1; i <= T; ++i) {
        solve(i);
    }

    return 0;
}

复杂度分析

时间复杂度: $O(T \cdot |s|)$ 对于每一个测试用例，我们都需要完整地遍历一次字符串 s 来统计各种成分的数量。如果字符串 s 的长度是 $|s|$ ，那么处理一个测试用例的时间复杂度就是 $O(|s|)$ 。总共有 T 个测试用例，所以总的时间复杂度就是 $O(T \cdot |s|)$ ，的说。
空间复杂度: $O(1)$ 在每个测试用例中，我们只使用了几个整数变量（harmful_count, dry_count, wet_count, total_len 等）来存储计数和长度。这些变量占用的空间是固定的，不随输入字符串 s 的长度变化而变化。所以，额外空间复杂度是 $O(1)$ ，非常节省内存呢，喵~

知识点总结

通过这道题，我们练习了几个非常实用的编程小技巧，要好好记住哦！

字符与索引的转换: char - 'a' 是一个处理小写字母的黄金技巧，可以快速地把 'a'~'z' 映射到 0~25 的整数索引。
模拟问题的核心思路: 仔细阅读题目，将规则分解成一个个清晰的步骤，然后用代码忠实地实现这些步骤。顺序很重要！
避免浮点数运算: 在处理比例或分数时，优先考虑使用交叉相乘等方法将其转换为整数运算。这可以避免浮点数潜在的精度问题，让程序更健壮、更快速。
代码风格: 将重复的逻辑封装成函数（比如 solve 函数），可以让 main 函数更清晰，代码结构也更好。

希望这篇题解能帮到你！继续加油，你超棒的，喵~ >w<

Garbage Classification - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：理解成分和类型的对应关系 ​

第二步：统计各类成分的数量 ​

第三步：应用分类规则（避免浮点数的小魔法！） ​

代码实现 ​

复杂度分析 ​

知识点总结 ​