刷题笔记合集🔗

数字涂色

问题描述

希望小学三年二班在疫情后重新开学，第一天的任务是重新制作黑板报。黑板上已经写了 个正整数，同学们需要给每个数上色。为了让黑板报既美观又有学习意义，老师要求同种颜色的所有数都可以被这种颜色中最小的那个数整除。请计算最少需要多少种颜色才能给这 个数上色。

输入格式

第一行包含一个正整数 ，表示黑板上数字的个数。

第二行包含 个用空格分隔的正整数，表示黑板上各个数字的值。

输出格式

输出一个整数，表示最少需要的颜色种数。

样例输入1

3
2 4 6

样例输出1

1

样例输入2

4
2 3 4 9

样例输出2

2

样例解释

数据范围

• 
• 每个数字

题解

数学+贪心

这道题目的核心在于理解"同种颜色的所有数都可以被这种颜色中最小的那个数整除"这个条件。解决这个问题的关键步骤如下：

1. 首先，将输入的数列进行升序排序。这样做的好处是，从左到右遍历时，当前数字一定是未处理数字中最小的。

2. 遍历排序后的数列，对于每个还没有被着色的数字，将它作为一种新颜色的最小数。

3. 然后，继续向右遍历，将所有能被这个最小数整除的数字都标记为这种颜色。

4. 重复步骤 2 和 3，直到所有数字都被着色。

5. 统计使用的颜色数量，即为答案。

这个方法之所以有效，是因为它保证了每种颜色的最小数一定是该颜色中所有数字的因子。同时，由于是按照升序遍历的，所以也保证了使用的颜色数量是最少的。

参考代码

• Python

def min_colors(n, numbers):
    # 对数字列表进行排序
    numbers.sort()
    
    # 初始化颜色数组，0表示未着色
    colors = [0] * n
    
    # 颜色计数器
    color_count = 0
    
    # 遍历所有数字
    for i in range(n):
        # 如果当前数字未着色
        if colors[i] == 0:
            # 使用新的颜色
            color_count += 1
            colors[i] = color_count
            
            # 将所有能被当前数字整除的未着色数字标记为相同颜色
            for j in range(i+1, n):
                if colors[j] == 0 and numbers[j] % numbers[i] == 0:
                    colors[j] = color_count
    
    # 返回使用的颜色数量
    return color_count

# 读取输入
n = int(input())
numbers = list(map(int, input().split()))

# 计算并输出结果
result = min_colors(n, numbers)
print(result)

• C

#include <stdio.h>
#include <stdlib.h>

// 比较函数，用于qsort
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int min_colors(int n, int *numbers) {
    // 对数字数组进行排序
    qsort(numbers, n, sizeof(int), compare);
    
    // 初始化颜色数组，0表示未着色
    int colors[100] = {0};  // 假设n最大为100
    
    // 颜色计数器
    int color_count = 0;
    
    // 遍历所有数字
    for (int i = 0; i < n; i++) {
        // 如果当前数字未着色
        if (colors[i] == 0) {
            // 使用新的颜色
            color_count++;
            colors[i] = color_count;
            
            // 将所有能被当前数字整除的未着色数字标记为相同颜色
            for (int j = i+1; j < n; j++) {
                if (colors[j] == 0 && numbers[j] % numbers[i] == 0) {
                    colors[j] = color_count;
                }
            }
        }
    }
    
    // 返回使用的颜色数量
    return color_count;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int numbers