Chương trình C++ kiểm tra mũ màu mèo có nhất quán không

Mô tả bài toán

Có N con mèo, mèo i nói: "Trong N-1 mũ của mèo khác, có đúng A[i] màu khác nhau". Kiểm tra có tồn tại gán màu mũ thỏa mãn không.

Ví dụ

A=[1,2,2]. Đầu ra: True (1) (màu: đỏ, xanh, xanh).

Thuật toán (Phân tích giá trị min/max)

1. Tìm mn = min(A), mx = max(A), cnt = số phần tử = mn.
2. Nếu : hợp lệ nếu (tất cả màu khác nhau) hoặc .
3. Nếu : hợp lệ nếu =cnt và = 2*(mx-cnt).
4. Ngược lại: false.

Đoạn mã C++

#include <bits/stdc++.h>
using namespace std;

bool solve(vector<int> A){
    int mn=1e9, mx=0, cnt=0, 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;
    return 0;
}

Đầu vào / Đầu ra

Input: {1,2,2}

Output: 1