คำชี้แจงปัญหา
ให้ N แก้วที่มีน้ำและรายการของความสามารถของพวกเขาแต่ละคน ภารกิจคือการหาจำนวนขวดขั้นต่ำที่จำเป็นในการกรอกแก้ว K ให้ถูกต้อง ความจุของแต่ละขวดคือ 100 หน่วย
ตัวอย่าง
ถ้า N =5, K =4, ความจุ[] ={1, 2, 3, 2, 1}.
- การเติมแก้วที่มีความจุ 2, 3, 2 ต้องใช้ 8 ชิ้น
- ทางนี้เปิดแค่ 1 ขวดก็พอ
อัลกอริทึม
- ในการกรอกแว่นตา K ให้ใส่แว่นตา K ที่มีความจุน้อยที่สุด
-
ขวดที่ต้องการทั้งหมดสามารถคำนวณได้ดังนี้ -
ค่าเพดานของ (ผลรวมของความจุของแก้วที่ 1 k) / (ความจุ 1 ขวด)
ตัวอย่าง
#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;
} ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
Min bottles required = 1
