Đề bài
Cho N ly có nước, và danh sách dung tích của từng ly. Nhiệm vụ là tìm số chai tối thiểu để điền đúng K ly. Dung tích mỗi chai là 100 đơn vị.
Ví dụ
Nếu N = 5, K = 4, capacity[] = {1, 2, 3, 2, 1}.
- Điền các ly dung tích 2, 3, 2 cần 8 đơn vị.
- Cách này chỉ cần mở 1 chai.
Thuật toán
- Để điền đúng K ly, lấy K ly có dung tích nhỏ nhất
- Tổng số chai cần tính bằng giá trị trần của (Tổng dung tích K ly đầu tiên) / (Dung tích 1 chai).
Ví dụ
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int minBottles(int *capacity, int n, int k) {
sort(capacity, capacity + n);
int sum = 0;
for (int i = 0; i < k; ++i) {
sum += capacity[i];
}
return ceil((double)sum / 100);
}
int main() {
int capacity[] = {1, 2, 3, 2, 1};
cout << "Số chai tối thiểu = " << minBottles(capacity, 5, 4) << endl;
return 0;
}
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Số chai tối thiểu = 1