Chương trình C ++ kiểm tra từ mèo có đúng hay không với mũ màu

Giả sử chúng ta có một mảng A với N phần tử. Xét có N con mèo và chúng được đánh số từ 1 đến N. Mỗi con mèo đội một chiếc mũ và con mèo thứ i nói "có chính xác A [i] số màu khác nhau trong số N-1 chiếc mũ mà các con mèo sở hữu, trừ tôi". Chúng tôi phải kiểm tra xem có tồn tại chuỗi màu sắc của mũ phù hợp với nhận xét của mèo hay không.

Vì vậy, nếu đầu vào là A =[1, 2, 2], thì đầu ra sẽ là Đúng, vì nếu mèo 1, 2 và 3 đội mũ có màu tương ứng là mũ đỏ, xanh lam và xanh lam, thì nó phù hợp với nhận xét của những con mèo.

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

mn := inf, mx = 0, cnt = 0
n := size of A
Define an array a of size (n + 1)
for initialize i := 1, when i <= n, update (increase i by 1), do:
   a[i] := A[i - 1]
   mn := minimum of mn and a[i]
   mx = maximum of mx and a[i]
for initialize i := 1, when i <= n, update (increase i by 1), do:
   if a[i] is same as mn, then:
      (increase cnt by 1)
   if mx is same as mn, then:
      if mn is same as n - 1 or 2 * mn <= n, then:
         return true
    Otherwise
return false
otherwise when mx is same as mn + 1, then:
   if mn >= cnt and n - cnt >= 2 * (mx - cnt), then:
      return true
   Otherwise
      return false
Otherwise
return false

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;
bool solve(vector<int> A) {
   int mn = 99999, mx = 0, cnt = 0;
   int n = A.size();
   vector<int> a(n + 1);
   for (int i = 1; i <= n; ++i) {
      a[i] = A[i - 1];
      mn = min(mn, a[i]), mx = max(mx, a[i]);
   }
   for (int i = 1; i <= n; ++i)
      if (a[i] == mn)
         ++cnt;
   if (mx == mn) {
      if (mn == n - 1 || 2 * mn <= n)
         return true;
      else
         return false;
   }
   else if (mx == mn + 1) {
      if (mn >= cnt && n - cnt >= 2 * (mx - cnt))
         return true;
      else
         return false;
   }
   else
      return false;
}
int main() {
   vector<int> A = { 1, 2, 2 };
   cout << solve(A) << endl;
}

Đầu vào

{ 1, 2, 2 }

Đầu ra

1