Re: [閒聊] 每日LeetCode已回收
875. Koko Eating Bananas
有 n 堆的香蕉，其中第 i 堆的香蕉有 piles[i] 個，
現在每小時可以選擇其中一堆並吃掉最多 k 個香蕉，
如果那堆不滿 k 個也只能吃掉那堆的全部，下一小時才能再選其他堆來吃。
給定 h 代表要在 h 小時內吃完 n 堆香蕉，求 k 的最小值是多少。
Constraints:
- 1 <= piles.length <= 10^4
- piles.length <= h <= 10^9
- 1 <= piles[i] <= 10^9
Example 1:
Input: piles = [3,6,7,11], h = 8
Output: 4
Explanation:
第一堆需要 1 小時 (4*0 < 3 <= 4*1)
第二堆需要 2 小時 (4*1 < 6 <= 4*2)
第三堆需要 2 小時 (4*1 < 7 <= 4*2)
第四堆需要 3 小時 (4*2 < 11 <= 4*3)
每小時吃 4 個剛好能在 8 小時內吃完 (且每小時吃 3 個不行)
Example 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30
Example 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23
解題思路:
若 k' 可以在 h 小時內吃完，則 k' + 1 也一定可以，
因為有單調性所以可以對答案做二分搜。
因為 h >= piles.length，所以每小時吃 max(piles) 一定可以在 h 小時內吃完，
每小時吃 0 個一定吃不完，
答案落在 (0, max(piles)]。
k' 能在 h 小時內吃完 if sum_i (ceil(piles[i] / k)) <= h，
注意整數除法會變整數跟加總可能會 overflow。
C++ code:
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int l = 0, r = *max_element(piles.begin(), piles.end());
while(l + 1 < r){
int mid = (l + r) / 2;
long long hours = 0;
for(auto p : piles){
hours += ceil((double)p / mid);
}
if(hours <= h) r = mid;
else l = mid;
}
return r;
}
};
---
補一下昨天的題目 基本上也是做法非常相似的題目
2187. Minimum Time to Complete Trips
有 n 台巴士，第 i 台需要花 time[i] 的時間完成一趟旅行，
每台巴士各自獨立可以同時旅行，並且完成一趟旅行後可以無縫繼續下次的旅行。
給定 totalTrips，求最少需要多少時間才會總共完成 totalTrips 次旅行。
Example 1:
Input: time = [1,2,3], totalTrips = 5
Output: 3
Explanation:
t = 3 時，
第一台巴士已經完成 3 次旅行，
第二台巴士已經完成 1 次旅行，
第三台巴士已經完成 1 次旅行，
總計完成 5 次旅行，
而 t = 2 時加總不足 5 次。
Example 2:
Input: time = [2], totalTrips = 1
Output: 2
解題思路:
當時間越多時，完成次數會非單調遞增，因此也可以對答案做二分搜。
當 t' = min(time) * totalTrips 時，一定可以完成 totalTrips 次，
當 t' = 0 時，一定不能完成 totalTrips 次 (0 < 1 <= totalTrips)，
答案落在 (0, min(time) * totalTrips]
t' 時可以完成 totalTrips 次旅行 if sum_i(floor(t'/time[i])) >= totalTrips，
因為取 floor 所以直接整數除法就好，注意數字範圍。
C++ code:
class Solution {
public:
long long minimumTime(vector<int>& time, int totalTrips) {
long long l = 0, r = (long long)*min_element(time.begin(),
time.end()) * totalTrips;
while(l + 1 < r){
long long mid = (l + r) / 2;
long long sum = 0;
for(auto t : time) sum += mid / t;
if(sum >= totalTrips) r = mid;
else l = mid;
}
return r;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1678235730.A.E7F.html
推
03/08 09:16,
2年前
, 1F
03/08 09:16, 1F
推
03/08 13:28,
2年前
, 2F
03/08 13:28, 2F
討論串 (同標題文章)
完整討論串 (本文為第 262 之 719 篇)：