华为OD 机试 2025-黑板上色

📝 题目描述：最少上色种数（整除分组）

疫情过后，希望小学终于又重新开学了，三年二班开学第一天的任务是将后面的黑板报重新制作。黑板上已经写上了 N 个正整数，同学们需要为这每个数分别涂上颜色。

为了让黑板报既美观又有学习意义，老师提出一个要求：

每一种颜色涂上的所有数，都必须能被该组中最小的那个数整除。

现在请你帮小朋友们计算一下：最少需要多少种颜色，才能满足上述要求。

---

📥 输入描述

• 第 1 行是一个正整数 N（1 ≤ N ≤ 100），表示数字个数。
• 第 2 行包含 N 个正整数 a₁, a₂, ..., aₙ，每个数的取值范围为 [1, 100]。

---

📤 输出描述

• 输出一个整数，表示满足题目要求所需的最少颜色种数。

---

📌 示例

示例 1

输入：

3
2 4 6

输出：

1

说明：
所有数字都能被 2 整除，因此只需要 1 种颜色。

---

示例 2

输入：

4
2 3 4 9

输出：

2

说明：
可以分为两组：

• 组1：2、4 → 4 能被 2 整除
• 组2：3、9 → 9 能被 3 整除

---

🧠 解题思路解析

1. 核心思想：贪心 + 分组

   • 每次从剩余的数字中选出最小的数字 x；
   • 将所有能被 x 整除的数，分为一组（同色），移除；
   • 重复上述操作，直到所有数都被分组。

2. 详细步骤：

   • 将输入数字去重，避免冗余；
   • 对数字排序，保证每次选的最小；
   • 用贪心策略依次分组，统计分组数量即为所需颜色数。

3. 时间复杂度：

   • 排序：O(N log N)，遍历：O(N²)（因为每次删除一个或多个元素），对 N ≤ 100 是可接受的。

---

✅ Python 实现

def min_colors(nums):nums = sorted(set(nums))  # 去重并排序count = 0while nums:base = nums[0]nums = [x for x in nums if x % base != 0]count += 1return countif __name__ == "__main__":N = int(input())nums = list(map(int, input().split()))print(min_colors(nums))

---

✅ Java 实现

import java.util.*;public class Main {public static int minColors(List<Integer> nums) {Set<Integer> set = new HashSet<>(nums);List<Integer> list = new ArrayList<>(set);Collections.sort(list);int count = 0;while (!list.isEmpty()) {int base = list.get(0);List<Integer> newList = new ArrayList<>();for (int num : list) {if (num % base != 0) newList.add(num);}list = newList;count++;}return count;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();List<Integer> nums = new ArrayList<>();for (int i = 0; i < N; i++) nums.add(sc.nextInt());System.out.println(minColors(nums));}
}

---

✅ JavaScript 实现（Node.js）

function minColors(nums) {nums = [...new Set(nums)].sort((a, b) => a - b);let count = 0;while (nums.length > 0) {const base = nums[0];nums = nums.filter(x => x % base !== 0);count++;}return count;
}// Node.js 读取输入
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });let input = [];
rl.on('line', line => {input.push(line.trim());if (input.length === 2) {const nums = input[1].split(' ').map(Number);console.log(minColors(nums));rl.close();}
});

---

🏁 总结

• 该问题是典型的整除分组 + 贪心策略；
• 每次贪心地用最小数去覆盖能整除的数，能有效减少颜色数；
• 本题由于数据规模较小，三种主流语言实现效率都较高，适合笔试/面试使用。

---