컬러 모자로 고양이 단어가 맞는지 아닌지 확인하는 C++ 프로그램

<시간/>

N개의 요소가 있는 배열 A가 있다고 가정합니다. N 고양이가 있고 1에서 N까지 번호가 매겨져 있다고 가정하십시오. 각 고양이는 모자를 쓰고 있고 i 번째 고양이는 "나를 제외하고 고양이가 소유한 N-1 모자 중 정확히 A[i]개의 다른 색상이 있습니다"라고 말합니다. 고양이들의 말과 일치하는 일련의 모자 색깔이 있는지 확인해야 합니다.

따라서 입력이 A =[1, 2, 2]와 같으면 출력은 True가 됩니다. 왜냐하면 고양이 1, 2 및 3이 각각 빨간색, 파란색 및 파란색 모자라는 색상의 모자를 쓰고 있다면 다음과 일치하기 때문입니다. 고양이들의 말.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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

입력

{ 1, 2, 2 }