Số chai tối thiểu cần thiết để đổ đầy K ly trong C ++

Tuyên bố vấn đề

Cho N cốc đựng nước và danh sách các dung tích của chúng. Nhiệm vụ là tìm số chai tối thiểu để điền đúng K ly. Sức chứa của mỗi chai là 100 chiếc.

Ví dụ

Nếu N =5, K =4, công suất [] ={1, 2, 3, 2, 1}.

• Đổ đầy kính có dung lượng 2, 3, 2, cần 8 đơn vị.
• Bằng cách này, chỉ cần mở 1 chai là đủ.

Thuật toán

• Để điền chính xác K kính, lấy K kính có dung lượng nhỏ nhất

• Tổng số chai cần thiết có thể được tính là -

  Giá trị trần của (Tổng dung tích của k ly thứ nhất) / (Dung tích của 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 << "Min bottles required = " <<minBottles(capacity, 5, 4) << endl;
   return 0;
}

Đầu ra

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 -

Min bottles required = 1