【华为OD机试真题 C++】数字涂色 【2022 Q4 | 100分】

■ 题目描述

【数字涂色】

疫情过后，希望小学终于又重新开学了，三年二班开学第一天的任务是将后面的黑板报重新制作。

黑板上已经写上了N个正整数，同学们需要给这每个数分别上一种颜色。

为了让黑板报既美观又有学习意义，老师要求同种颜色的所有数都可以被这种颜色中最小的那个数整除。

现在请你帮帮小朋友们，算算最少需要多少种颜色才能给这N个数进行上色。

输入描述

第一行有一个正整数N，其中。

第二行有N个int型数(保证输入数据在[1,100]范围中)，表示黑板上各个正整数的值。

输出描述

输出只有一个整数，为最少需要的颜色种数。

示例1 输入输出示例仅供调试，后台判题数据一般不包含示例

输入

3

2 4 6

输出

1

说明

所有数都能被2整除

示例2 输入输出示例仅供调试，后台判题数据一般不包含示例

输入

4

2 3 4 9

输出

2

说明

2与4涂一种颜色，4能被2整除；

3与9涂另一种颜色，9能被3整除。

不能4个数涂同一个颜色，因为3与9不能被2整除。所以最少的颜色是两种。

C++代码实现1：

#include <bits/stdc++.h>
using namespace std;
void Split(string input, vector<int> &output, char patten)
{
string one_word;
int j = 0;
input += patten;
for (int i = 0; i < input.size(); i++) {
if (input[i] == patten) {
one_word = input.substr(j, i - j);
output.push_back(stoi(one_word));
one_word.clear();
j = i + 1;
}
}
}
void Classify(vector<int> nums_vec, vector <string> &output)
{
while (!nums_vec.empty()) {
int temp = nums_vec[0];
string temp_string = "[";
for (int i = 0; i < nums_vec.size(); i++) {
if (nums_vec[i] % temp == 0) {
temp_string += to_string(nums_vec[i]);
if (i < nums_vec.size() - 1) {
temp_string += ",";
}
nums_vec.erase(nums_vec.begin() + i);
i--;
}
}
if (temp_string.back() == ',') {
temp_string.erase(temp_string.size() - 1);
}
temp_string += "]";
output.push_back(temp_string);
}
}
int main(int argc, char **argv)
{
int N;
while (cin >> N) {
vector<int> nums(N);
for (int i = 0; i < N; i++) {
cin >> nums[i];
}
sort(nums.begin(), nums.end());
vector <string> outputs;
Classify(nums, outputs);
cout << outputs.size() << endl;
}
return 0;
}

C++代码实现2：

#include<bits/stdc++.h>
using namespace std;
int main()
{
// 处理输入
int N;
cin >> N;
vector<int> nums;
for (int i = 0; i < N; i++) {
int a;
cin >> a;
nums.push_back(a);
}
int res = 0;
//用一个标记数组来说明这个数是否已经能被其他数整除了
vector<bool> dp(nums.size(), false);
for (int i = 0; i < nums.size(); ++i) {
//能整除的话，直接跳过就可以
if (dp[i]) {
continue;
}
for (int j = i + 1; j < nums.size(); ++j) {
if (nums[j] % nums[i] == 0) {
dp[j] = true;
}
}
res++;
}
cout << res;
return 0;
}

最后

以上就是追寻小蘑菇最近收集整理的关于【华为OD机试真题 C++】数字涂色 【2022 Q4 | 100分】的全部内容，更多相关【华为OD机试真题内容请搜索靠谱客的其他文章。