题目描述
疫情过后,希望小学终于又重新开学了,三年二班开学第一天的任务是将后面的黑板报重新制作。
黑板上已经写上了N个正整数,同学们需要给这每个数分别上一种颜色。
为了让黑板报既美观又有学习意义,老师要求同种颜色的所有数都可以被这种颜色中最小的那个数整除。
现在请你帮帮小朋友们,算算最少需要多少种颜色才能给这N个数进行上色。
输入描述
第一行有一个正整数N,其中。
第二行有N个int型数(保证输入数据在[1,100]范围中),表示黑板上各个正整数的值。
输出描述
输出只有一个整数,为最少需要的颜色种数。
用例
输入 |
3 |
输出 | 1 |
说明 | 所有数都能被2整除 |
输入 | 4 2 3 4 9 |
输出 | 2 |
说明 | 2与4涂一种颜色,4能被2整除;3与9涂另一种颜色,9能被3整除。不能4个数涂同一个颜色,因为3与9不能被2整除。所以最少的颜色是两种。 |
题目解析
简单的逻辑题,题目要求:“同种颜色的所有数都可以被这种颜色中最小的那个数整除”。
因此我们可以直接将输入数列进行升序排序,则数列从左到右,元素依次增大,我们每次取最左边的数arr[i],然后遍历它后面的所有数arr[j]去除它,若可以整除,则为一种颜色,若不可以整除,则为不同颜色。
本题难点主要在于,如何标记一个元素已经涂色了,我这里直接定义了一个长度和输入数列arr相同的数组color,color所有元素默认未初始化,一旦arr[j]可以整除arr[i],则color[j] = true。
Java算法源码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
System.out.println(getResult(n, arr));
}
public static int getResult(int n, int[] arr) {
Arrays.sort(arr);
if (arr[0] == 1) {
return 1;
}
boolean[] color = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (color[i]) continue;
color[i] = true;
for (int j = i + 1; j < n; j++) {
if (!color[j] && arr[j] % arr[i] == 0) {
color[j] = true;
}
}
count++;
}
return count;
}
}
JS算法源码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 2) {
let n = parseInt(lines[0]);
let arr = lines[1].split(" ").slice(0, n);
console.log(getMinColorCount(arr));
lines.length = 0;
}
});
function getMinColorCount(arr) {
arr.sort((a, b) => a - b);
if (arr[0] === 1) {
return 1;
}
let color = new Array(arr.length);
let count = 0;
for (let i = 0; i < arr.length; i++) {
if (color[i]) continue;
color[i] = true;
for (let j = i + 1; j < arr.length; j++) {
if (!color[j] && arr[j] % arr[i] === 0) {
color[j] = true;
}
}
count++;
}
return count;
}
Python算法源码
# 输入获取
n = int(input())
arr = list(map(int, input().split()))
# 算法入口
def getResult():
arr.sort()
if arr[0] == 1:
return 1
color = [False]*n
count = 0
for i in range(n):
if color[i]:
continue
color[i] = True
for j in range(i+1, n):
if not color[j] and arr[j] % arr[i] == 0:
color[j] = True
count += 1
return count
# 调用算法
print(getResult())
C算法源码
#include <stdio.h>
#include <stdlib.h>
int getResult(int nums[], int nums_size);
int cmp(const void* a, const void* b) {
return (*(int*) a) - (*(int*) b);
}
int main() {
int n;
scanf("%d", &n);
int nums[n];
for(int i=0; i<n; i++) {
scanf("%d", &nums[i]);
}
printf("%dn", getResult(nums, n));
return 0;
}
int getResult(int nums[], int nums_size) {
qsort(nums, nums_size, sizeof(int), cmp);
if(nums[0] == 1) {
return 1;
}
int* color = (int*) calloc(nums_size, sizeof(int));
int count = 0;
for(int i=0; i<nums_size; i++) {
if(color[i]) continue;
color[i] = 1;
for(int j=i+1; j<nums_size; j++) {
if(!color[j] && nums[j] % nums[i] == 0) {
color[j] = 1;
}
}
count++;
}
return count;
}
免责声明:
1、IT资源小站为非营利性网站,全站所有资料仅供网友个人学习使用,禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享,本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题,请立即告知本站,本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体,但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员,一律视为同意网站规定,本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文
评论0