【HT-050-Rainbow】彩虹组周赛A题解析

题意

在暮色森林中住着一只谜题羊，它有个特殊要求：
你需要提供十六色的羊毛各一块才能获得神奇妙妙奖励。

但问题在于，你初始准备并不齐全所有颜色的羊毛。所幸的是，你手上有一些羊毛和染料，并且可以进行如下转换：

• 转换规则： 将一块任意颜色的羊毛与一份染料结合，可以得到染料颜色的羊毛；转换后原先的羊毛和染料都会被消耗掉。

输入格式：

• 第一行输入一个正整数 T，表示测试数据的组数。
• 对于每组测试数据：
  • 第一行给出 16 个正整数 a₁, a₂, …, a₁₆，表示每种颜色羊毛的数量。
  • 第二行给出 16 个正整数 b₁, b₂, …, b₁₆，表示每种颜色染料的份数。

输出格式：

• 对于每组测试数据，如果你能通过转换后获得十六种颜色的羊毛各一块，输出 Yes；否则输出 No。

关键点总结：

• 如果已有一种颜色的羊毛至少有一块，则这一颜色无需转换；如果数量超过 1，则多余的部分可作为转换的材料。

• 对于缺失羊毛的颜色，必须确保你拥有至少一份对应颜色的染料来支持转换。

• 最终，只需要保证“多余羊毛的总数”足够转换补全所有缺失颜色即可获得奖励。

---

解析

1. 输入部分与测试用例循环

输入我觉得没必要讲了吧……

2. 读入材料数据

vector<int> wool(16), dye(16);
for (int i = 0; i < 16; i++) {
    cin >> wool[i];
}
for (int i = 0; i < 16; i++) {
    cin >> dye[i];
}
CPP

• 作用：
  • 定义两个长度均为 16 的数组，wool 用于记录 16 种颜色羊毛的数量，dye 用于记录对应颜色染料的数量。
  • 依次读入相关数据，为后续的判断做准备。

3. 初始化统计变量

int need = 0;
int more = 0;
bool flag = true;
CPP

• 作用：
  • need： 用于统计需要通过转换获得羊毛的颜色数，即那些原始羊毛数量为 0 的颜色。
  • more： 用于累计所有颜色中多余的羊毛数量。计算方式是每种颜色保留一块羊毛作为最终需求，多余部分 (wool[i] - 1) 可作为转换原料。
  • flag： 用来标识是否遇到无法满足转换条件的情况（例如：缺失的颜色没有对应至少一份染料），一旦出现这种情况则无需继续判断。

4. 遍历各颜色，统计缺失与多余资源

for (int i = 0; i < 16; i++){
    if(wool[i] == 0) {
        if(dye[i] < 1) {
            flag = false;
            break;
        }
        need++;  // 记录该颜色缺失，需要转换获得一块
    } else {
        more += (wool[i] - 1);  // 累计多余的羊毛数量（超过一块的部分）
    }
}
CPP

• 作用：
  • 遍历 16 种颜色：
    • 当羊毛数量为 0：
      • 必须依靠转换获得此颜色的羊毛，因此首先检查对应染料是否足够（必须至少为 1）。
      • 若染料不足，则 flag 设为 false，直接退出循环，因为这种情况下不可能补全所有颜色。
      • 如果染料充足，则将 need 加 1，表示需要一次转换操作。
    • 当羊毛数量大于 0：
      • 至少有一块羊毛已符合要求，多余的部分（wool[i] - 1）则可以用于转换其他缺失颜色。

5. 最终判断与输出

if(flag && more >= need)
    cout << "Yes" << "\n";
else
    cout << "No" << "\n";
CPP

• 作用：
  • 第一步： 判断 flag 是否仍然为 true，保证所有缺失的颜色都有对应充足的染料支持转换。
  • 第二步： 检查统计的多余羊毛数量 more 是否足够补偿所有缺失颜色的需求 need。
  • 如果两者条件同时满足，则说明可以通过转换获得完整的十六色羊毛，输出 Yes；否则输出 No。

---

总结

1. 题意总结：
   利用手头上的羊毛和染料，通过转换操作补全缺失的颜色，最终达到十六种颜色羊毛各一块以获得奖励。

2. 解题思路：

   • 统计现状： 检查每种颜色是否已有羊毛，若无则判断染料是否充足，并记录需要转换的次数。
   • 转换资源： 多余羊毛（每种颜色超过一块的部分）可以作为转换的原材料。
   • 条件判断： 最终只需确保每个缺失颜色都有染料支持，并且总多余羊毛数足够转换所有缺失需求，即可满足条件。

这样一来，整个流程就能判断出题人是否能利用现有羊毛和染料，经过有限的转换操作，成功获得神奇妙妙奖励（吐槽：谁取得这个名字，跟米奇妙妙屋似的）。

标程

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        vector<int> wool(16), dye(16);
        for (int i = 0; i < 16; i++) {
            cin >> wool[i];
        }
        for (int i = 0; i < 16; i++) {
            cin >> dye[i];
        }
        int need = 0;
        int more = 0;
        bool flag = true;
        for (int i = 0; i < 16; i++){
            if(wool[i] == 0) {
                if(dye[i] < 1) {
                    flag = false;
                    break;
                }
                need++;
            } else {
                more += (wool[i] - 1);
            }
        }
        
        if(flag && more >= need)
            cout << "Yes" << "\n";
        else
            cout << "No" << "\n";
    }
    return 0;
}

CPP