C++でバナナを食べるココ

バナナの山がN個あるとすると、i番目の山にはバナナの山があります[i]。ここで警備員は去り、H時間後に戻ってきます。ココは、1時間あたりのバナナの食べる速度をKと決めることができます。毎時、彼女はバナナの山をいくつか取り、その山からK本のバナナを食べます。パイルのバナナがK未満の場合、彼女は代わりにすべてのバナナを消費し、この時間中はそれ以上バナナを食べません。ココはゆっくり食べるのが好きですが、警備員が戻ってくる前にすべてのバナナを食べ終えたいと考えています。彼女がH時間以内にすべてのバナナを食べることができるように、最小の整数Kを見つける必要があります。

したがって、入力が[3,6,7,11]のようで、H =8の場合、出力は4になります。

これを解決するには、次の手順に従います-

• ok（）というメソッドを定義します。これは、配列a、2つの値xおよびhを取ります

• 時間：=0

• 0からaのサイズまでの範囲のiの場合

  • 時間：=時間+ a [i] / x

  • time：=time + i（a [i] modxが0の場合）

• 時間<=H

  のときにtrueを返します

• メインの方法から次のようにします

• n：=杭配列のサイズ、合計を設定：=0、低：=1、高：=0

• 0からn–1の範囲のiの場合

  • 高い：=杭の最大値[i]および高い

• 低<高

  • mid：=low +（high – low）/ 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

出力

4