โปรแกรม C++ ตรวจสอบความสอดคล้องของสีหมวกแมว

มี N ตัวแมว แต่ละตัวสวมหมวกสีหนึ่ง ตัวที่ i พูดว่า "ในหมวกของแมวอื่น N-1 ตัว มีสีที่แตกต่างกันทั้งหมด A[i] สี" ต้องการตรวจสอบว่ามีการจัดสีหมวกที่สอดคล้องกับข้อความทุกตัวหรือไม่

ตัวอย่าง: A=[1,2,2] ผลลัพธ์: True (1) (เช่น แมว 1 สีแดง, แมว 2-3 สีน้ำเงิน → แมว 1 เห็น 1 สี, แมว 2-3 เห็น 2 สี)

ขั้นตอนการแก้ปัญหา (Case Analysis)

1. หา mn = min(A), mx = max(A), cnt = จำนวน A[i] == mn
2. กรณี mx == mn:
   • ถ้า mn == N-1 (ทุกตัวเห็นสีต่างกันหมด) หรือ 2*mn ≤ N → true
   • มิฉะนั้น false
3. กรณี mx == mn + 1:
   • ถ้า mn ≥ cnt และ N - cnt ≥ 2*(mx - cnt) → true
   • มิฉะนั้น false
4. กรณีอื่น → false

ตัวอย่างโค้ด C++

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

อินพุต / เอาต์พุต

Input: {1, 2, 2}

Output: 1