Thỏ trong rừng C++ (Rabbits in Forest)

Mỗi thỏ báo cáo số thỏ khác cùng màu. Cho mảng answers[], tìm số thỏ tối thiểu trong rừng.

Ví dụ

Input - [1,1,2] Output - 5

Giải thích - 2 thỏ trả lời "1" có thể cùng màu (tổng 2 con). Thỏ trả lời "2" màu khác → cần thêm 2 thỏ không trả lời. Tổng: 3 trả lời + 2 không trả lời = 5.

Phương pháp tiếp cận (Map đếm nhóm)

• Map m[x] = số thỏ đã đếm trong nhóm size x+1
• Duyệt answers:
  • x=0: count++ (thỏ đơn độc)
  • Nếu m[x] chưa có: tạo nhóm mới size x+1, count += x+1, m[x]=0
  • Ngược lại: m[x]++, nếu m[x]==x → nhóm đầy, xóa m[x]

Ví dụ code C++

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

class Solution {
public:
    int numRabbits(vector<int>& ans) {
        map<int, int> m;
        int n = ans.size(), ret = 0;
        for (int x : ans) {
            if (x == 0) { ret++; continue; }
            if (!m.count(x)) {
                ret += x + 1;
                m[x] = 0;
            } else {
                m[x]++;
                if (m[x] == x) m.erase(x);
            }
        }
        return ret;
    }
};

int main() {
    vector<int> v = {1, 1, 2};
    Solution ob;
    cout << ob.numRabbits(v);
    return 0;
}

Kết quả

5