数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++代码用于有效地计算元素着色方案
假设我们有一个包含n个元素的数组A。我们需要用颜色对元素进行着色，使得：
对于任何一种颜色，所有该颜色的元素都必须能被该颜色元素中的最小值整除。
使用的颜色数量应最小化。
我们必须找到以有效方式对所有给定数字进行着色的最小颜色数。
因此，如果输入类似于A = [10, 2, 3, 5, 4, 2]，则输出将为3，因为第一种颜色用于元素A[0]和A[3]，第二种颜色用于元素A[2]，第三种颜色用于其余三个元素。
步骤
为了解决这个问题，我们将遵循以下步骤：
n := size of A ans := 0 sort the array A for initialize i := 0, when i < n, update (increase i by 1), do: ok := 1 for initialize j := 0, when j < i, update (increase j by 1), do: ok := ok AND (1 if A[i] mod A[j] is not 0, otherwise 0) ans := ans + ok return ans
示例
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int n = A.size();
int ans = 0;
sort(A.begin(), A.end());
for (int i = 0; i < n; i++){
int ok = 1;
for (int j = 0; j < i; j++)
ok &= (A[i] % A[j] != 0);
ans += ok;
}
return ans;
}
int main(){
vector<int> A = { 10, 2, 3, 5, 4, 2 };
cout << solve(A) << endl;
}输入
{ 10, 2, 3, 5, 4, 2 }输出
3
更新于：2022年3月29日
210 次浏览
广告