C++로 바나나를 먹는 코코

<시간/>

N개의 바나나 더미가 있다고 가정하고 i번째 더미에는 [i]개의 바나나가 있습니다. 여기 경비병이 갔고 H 시간 안에 돌아올 것입니다. Koko는 시간당 바나나 먹는 속도를 K로 결정할 수 있습니다. 매시간 그녀는 바나나 더미를 가져와서 그 더미에서 K 바나나를 먹습니다. 더미에 K개 미만의 바나나가 있는 경우 그녀는 대신 바나나를 모두 소비하고 이 시간 동안 더 이상 바나나를 먹지 않습니다. Koko는 천천히 먹는 것을 좋아하지만 경비원이 돌아오기 전에 바나나를 다 먹고 싶어한다고 생각해 보십시오. 우리는 그녀가 H 시간 내에 모든 바나나를 먹을 수 있도록 최소 정수 K를 찾아야 합니다.

따라서 입력이 [3,6,7,11]이고 H =8이면 출력은 4가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ok()라는 메서드를 정의합니다. 이것은 배열 a, 두 개의 값 x 및 h
를 취합니다.
시간 :=0
범위 0에서
크기까지의 i에 대해
- 시간 :=시간 + a[i] / x
- time :=time + i 일 때 a[i] mod x가 0
시간 <=H
일 때 true를 반환합니다.
기본 방법에서 다음을 수행하십시오.
n :=파일 배열의 크기, set sum :=0, low :=1, high :=0
0 ~ n – 1 범위의 i에 대해
- 높음 :=더미의 최대값[i] 및 높음
낮음 <높음
동안
- 중간 :=낮음 + (높음 – 낮음 ) /2
- ok(piles, mid, H)가 true이면 high로 설정 :=mid, 그렇지 않으면 low :=mid + 1
- ok(piles, mid, H)가 true이면 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