Mã C ++ để đếm màu để tô các phần tử theo cách hợp lệ

Giả sử chúng ta có một mảng A với n phần tử. Chúng ta cần sơn các phần tử bằng màu sắc sao cho -

• Nếu chúng ta xem xét bất kỳ màu nào, tất cả các phần tử của màu này phải chia hết cho khối lượng tối thiểu của cùng một màu.

• Số lượng màu được sử dụng nên được giảm thiểu.

Chúng ta phải tìm số lượng màu tối thiểu để tô tất cả các số đã cho một cách hợp lệ.

Vì vậy, nếu đầu vào là A =[10, 2, 3, 5, 4, 2], thì đầu ra sẽ là 3, vì sơn màu đầu tiên cho các phần tử A [0] và A [3], sơn màu thứ hai cho các phần tử A [2] và tô màu thứ ba cho ba phần tử còn lại.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

{ 10, 2, 3, 5, 4, 2 }

Đầu ra

3