สมมติว่าเรามีกล้วย N กอง กองที่ i มีกล้วย ที่นี่ยามไปแล้วและจะกลับมาในชั่วโมง H Koko สามารถกำหนดความเร็วในการกินกล้วยต่อชั่วโมงของเธอได้คือ K ในแต่ละชั่วโมง เธอหยิบกล้วยกองหนึ่งไปกิน K กล้วยจากกองนั้น ถ้ากองกล้วยมีน้อยกว่า K เธอก็กินกล้วยทั้งหมดแทน และจะไม่กินกล้วยอีกในชั่วโมงนี้ คิดซะว่าโคโคะชอบกินช้าๆ แต่ก็ยังอยากกินกล้วยให้หมดก่อน รปภ.จะกลับมา เราต้องหาจำนวนเต็ม K ขั้นต่ำเพื่อให้เธอกินกล้วยหมดภายใน H ชั่วโมง
ดังนั้นหากอินพุตเป็น [3,6,7,11] และ H =8 เอาต์พุตจะเป็น 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดวิธีการที่เรียกว่า ok() ซึ่งจะใช้อาร์เรย์ a สองค่า x และ h
-
เวลา :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของ a
-
เวลา :=เวลา + a[i] / x
-
เวลา :=เวลา + i เมื่อ a[i] mod x เป็น 0
-
-
คืนค่าจริงเมื่อเวลา <=H
-
จากวิธีหลักให้ทำดังนี้
-
n :=ขนาดของอาร์เรย์ไพล์, set sum :=0, ต่ำ :=1, สูง :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึง n – 1
-
สูง :=สูงสุดของกอง[i] และสูง
-
-
ในขณะที่ต่ำ <สูง
-
กลาง :=ต่ำ + (สูง – ต่ำ ) /2
-
ถ้า ok(piles, mid, H) เป็นจริง ให้ตั้งค่า high :=mid, มิฉะนั้น low :=mid + 1
-
ถ้า ok(piles, mid, H) เป็นจริง ให้ตั้งค่า high :=mid, มิฉะนั้น low :=mid + 1
-
-
ผลตอบแทนสูง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
bool ok(vector <int>& a, int x, int H){
int time = 0;
for(int i = 0; i < a.size(); i++){
time += a[i] / x;
time += (a[i] % x ? 1 : 0);
}
return time <= H;
}
int minEatingSpeed(vector<int>& piles, int H) {
int n = piles.size();
lli low = 1;
lli sum = 0;
lli high = 0;
for(int i = 0; i < n; i++)high = max((lli)piles[i], high);
while(low < high){
int mid = low + (high - low) / 2;
if(ok(piles, mid, H)){
high = mid;
}else{
low = mid + 1;
}
}
return high;
}
};
main(){
vector<int> v = {3,6,7,11};
Solution ob;
cout << (ob.minEatingSpeed(v, 8));
} อินพุต
[3,6,7,11] 8
ผลลัพธ์
4
