資料結構
網路
關係資料庫管理系統(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 次瀏覽
廣告