ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่ประกอบด้วย n องค์ประกอบและจำนวนเต็ม h แต่ละองค์ประกอบของอาร์เรย์ arr[] มีจำนวนงานที่รอดำเนินการสำหรับบุคคลนั้นและ H คือเวลาที่เหลือในการทำงานให้เสร็จ (เป็นชั่วโมง) งานของเราคือค้นหาความเร็วขั้นต่ำเพื่อจบงานทั้งหมด
คำอธิบายปัญหา :เราจำเป็นต้องค้นหาจำนวนงานที่บุคคลต้องทำให้เสร็จในหนึ่งชั่วโมงเพื่อให้งานทั้งหมดที่ระบุในอาร์เรย์เสร็จสมบูรณ์ในชั่วโมง H ถ้าเขาสามารถทำงานทั้งหมดที่ระบุใน arr[i] ได้ภายในเวลาไม่ถึงชั่วโมง เราจะนั่งพักผ่อนตามอัธยาศัย และหลังจากสิ้นสุดชั่วโมง ย้ายไปที่งานชุดถัดไป
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {4, 5, 1, 7, 8}, H = 5 ผลลัพธ์
8
คำอธิบาย
บุคคลนั้นต้องทำงานให้เสร็จ 5 ชุดใน 5 ชั่วโมง ดังนั้น เขา/เธอจึงต้องสร้างชุดที่มีจำนวนงานสูงสุดใน 1 ชั่วโมง ซึ่งจะเป็นความเร็วของเขา/เธอ
แนวทางการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราต้องหาความเร็วขั้นต่ำที่เขาสามารถทำงานทั้งหมดได้ ดังนั้น เราจะพบค่าแรกที่บุคคลสามารถทำได้ทั้งหมดคือระยะเวลาที่กำหนด
เราจะค้นหาความเร็วภายในช่วง 1 ถึงจำนวนสูงสุด ของงานที่ต้องทำในครั้งเดียว เนื่องจากค่านี้อาจมีขนาดใหญ่ เราจะใช้การค้นหาแบบไบนารีเพื่อความสะดวกในการคำนวณ
ในการตรวจสอบว่าด้วยความเร็วปัจจุบัน บุคคลสามารถแก้ปัญหาได้หรือไม่ เราจะหาเวลาที่ใช้ในการทำให้ครบชุดหนึ่งแล้วจึงบวกเวลาสำหรับชุดทั้งหมด หากเวลานี้น้อยกว่า H ก็ไม่สามารถทำได้
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
bool canDoJobInTime(int A[], int n, int H, int speed) {
int timeTaken = 0;
for (int i = 0; i < n; ++i)
timeTaken += (A[i] - 1) / speed + 1;
return timeTaken <= H;
}
int calcJobMinSpeed(int A[], int n, int H) {
if (H < n)
return -1;
int maxJob = A[0];
for(int i = 1; i < n; i++)
maxJob = max(A[i], maxJob);
int start = 1, end = maxJob;
while (start < end) {
int mi = start + (end - start) / 2;
if (!canDoJobInTime(A, n, H, mi))
start = mi + 1;
else
end = mi;
}
return start;
}
int main() {
int A[] = { 3, 6, 7, 11 }, H = 8;
int n = sizeof(A) / sizeof(A[0]);
cout<<"The minimum speed to finish all jobs in time is "<<calcJobMinSpeed(A, n, H);
return 0;
} ผลลัพธ์
The minimum speed to finish all jobs in time is 4
