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