华为OD 机试 2025-黑板上色-EW帮帮网

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

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

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

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

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

📥 输入描述

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

📤 输出描述

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

📌 示例

示例 1

输入：

3
2 4 6

输出：

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

示例 2

输入：

4
2 3 4 9

输出：

说明：
可以分为两组：

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

🧠 解题思路解析

核心思想：贪心 + 分组
- 每次从剩余的数字中选出最小的数字 x；
- 将所有能被 x 整除的数，分为一组（同色），移除；
- 重复上述操作，直到所有数都被分组。
详细步骤：
- 将输入数字去重，避免冗余；
- 对数字排序，保证每次选的最小；
- 用贪心策略依次分组，统计分组数量即为所需颜色数。
时间复杂度：
- 排序：O(N log N)，遍历：O(N²)（因为每次删除一个或多个元素），对 N ≤ 100 是可接受的。

✅ Python 实现

def min_colors(nums):
    nums = sorted(set(nums))  # 去重并排序
    count = 0
    while nums:
        base = nums[0]
        nums = [x for x in nums if x % base != 0]
        count += 1
    return count

if __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();
  }
});

🏁 总结

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

在这里插入图片描述

华为OD 机试 2025-黑板上色