ปัญหา
กระต่ายแต่ละตัวบอกว่ามีอีกกี่ตัวที่มีสีเดียวกัน (คำตอบใน Array answers) หา จำนวนกระต่ายน้อยที่สุด ในป่า
ตัวอย่าง: [1,1,2] → 5 ตัว
สองตัวตอบ 1 → อาจเป็นสีเดียวกัน (2 ตัว) ตัวตอบ 2 → ต้องมีอีก 2 ตัวสีเดียวกัน (รวม 3 ตัว) → 2+3=5
แนวคิด: Grouping by Answer
Logic
ถ้ากระต่ายตอบ x → กลุ่มสีนั้นมี x+1 ตัว
- ถ้ามี
cตัวตอบx→ ต้องการceil(c / (x+1))กลุ่ม → รวมceil(c / (x+1)) * (x+1)ตัว
โค้ด C++ (Optimized)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numRabbits(vector<int>& answers) {
unordered_map<int, int> count;
for (int x : answers) count[x]++;
int total = 0;
for (auto& [x, c] : count) {
int groupSize = x + 1;
int groups = (c + groupSize - 1) / groupSize; // ceil division
total += groups * groupSize;
}
return total;
}
};
int main() {
Solution ob;
vector<int> v = {1, 1, 2};
cout << ob.numRabbits(v); // 5
return 0;
}
การทำงานตัวอย่าง [1,1,2]
| Answer (x) | Count (c) | Group Size (x+1) | Groups (ceil) | Rabbits |
|---|---|---|---|---|
| 1 | 2 | 2 | 1 | 2 |
| 2 | 1 | 3 | 1 | 3 |
| Total | 5 |
ความซับซ้อน
- Time: O(n)
- Space: O(unique answers) ≤ O(n)
Input / Output
Input: [1,1,2]
Output: 5
