countKangaroos
Có n chú chuột túi với túi ở trước bụng. Mỗi chú chuột túi có 1 kích thước khác nhau (kích thước là số nguyên). Một chú chuột túi có thể nhảy vào túi của chú chuột túi khác nếu và chỉ nếu kích thước của chú chuột túi mà giữ chú chuột túi khác ở trong phải lớn hơn ít nhất là gấp đôi với kích thước của chú chuột túi nhảy vào.
Mỗi chú chuột túi có thế giữ nhiều nhất một chú chuột túi khác và chú chuột túi được nhảy vào túi thì không thể giữ thêm chú chuột túi khác.
Chú chuột túi mà được nhảy vào túi thì không thể được nhìn thấy từ bên ngoài. Hãy tìm cách để các chú chuột túi chui vào túi chú chuột túi khác sao cho số chú chuột túi được nhìn thấy là nhỏ nhất.
Ví dụ
- Với
n = 3vàs = [1, 2, 3], đầu ra làcountKangaroos(n, s) = 2
Đầu vào/Đầu ra
-
[giới hạn thời gian chạy] 0.5 giây
-
[input] integer n, array.integers s
Điều kiện tiền đề:
1 ≤ n ≤ 100
1 <= s[i] <= 1000. - [Đầu ra]
Một số nguyên thể hiện số chuột túi tối ưu cho bài toán.
Post Comment