Thỏ trong rừng trong C ++

Giả sử Trong một khu rừng, mỗi con thỏ có một số màu. Bây giờ một số tập hợp con thỏ (có thể là tất cả chúng) sẽ cho chúng ta biết có bao nhiêu con thỏ khác có cùng màu với chúng. Những câu trả lời đó được đặt trong một mảng. Chúng ta phải tìm số lượng thỏ tối thiểu có thể có trong rừng. Vì vậy, nếu đầu vào là [1,1,2], thì đầu ra sẽ là 5, vì hai con thỏ trả lời "1" có thể cùng màu, tức là màu trắng. Bây giờ con thỏ hơn câu trả lời "2" không thể là màu trắng hoặc các câu trả lời sẽ không nhất quán. Nói con thỏ trả lời "2" là màu đen. Sau đó, sẽ có 2 con thỏ đen khác trong rừng không trả lời vào mảng. Vì vậy, số thỏ nhỏ nhất có thể có trong rừng là 5:3 đã trả lời cộng với 2 thì không.

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

• tạo một ánh xạ m và n:=kích thước của mảng ans
• đặt ret là 0
• cho tôi trong phạm vi từ 0 đến n - 1
  • x:=ans [i]
  • nếu x =0, sau đó tăng ret lên 1 và bỏ qua phần tiếp theo của lần lặp này.
  • nếu m có x, sau đó tăng ret lên (x + 1), đặt m [x]:=0
  • nếu không thì
    • tăng m [x] lên 1
    • nếu m [x] =x, thì hãy xóa x khỏi m
• trả lời lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int numRabbits(vector<int>& ans) {
      map <int, int> m;
      int n = ans.size();
      int ret = 0;
      for(int i = 0; i < n; i++){
         int x = ans[i];
         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;
   }
};
main(){
   vector<int> v = {1,1,2};
   Solution ob;
   cout << (ob.numRabbits(v));
}

Đầu vào

[1,1,2]

Đầu ra

5