チョコレートをC++で分割する

いくつかのチャンクで構成されるチョコレートバーが1つあるとします。各チャンクには、甘さと呼ばれるリストによって与えられる独自の甘さがあります。 K人の友達の間でチョコレートを共有したいので、Kカットを使用してチョコレートバーをK + 1ピースにカットし始めると、各ピースはいくつかの連続したチャンクで構成されます。総甘さを最小限に抑えた作品を取り出し、他の作品を友達にあげれば。チョコレートバーを最適にカットすることで、得られる最大の総甘さを見つける必要があります。

したがって、入力が甘さ=[1,2,3,4,5,6,7,8,9]、K =5のようである場合、チョコレートを[1,2に分割できるため、出力は6になります。 、3]、[4,5]、[6]、[7]、[8]、[9]これらのピース。

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

• 関数ok（）を定義します。これは、配列v、cuts、maxVal、

  を取ります。

• カウンター：=0、温度：=0

• 初期化i：=0の場合、i <=vのサイズの場合、更新（iを1増やします）、実行-

  • temp> =maxValの場合、

    • （カウンターを1増やします）

    • temp：=0

  • iがvのサイズと同じである場合、-

    • ループから出てきます

  • temp：=temp + v [i]

• カウンター>=カット

  の場合はtrueを返します

• メインの方法から、次の手順を実行します。

• maxa：=-1

• n：=sのサイズ

• 低：=0、高：=0

• 初期化i：=0の場合、i

  • low：=lowとs[i]

    の最小値

  • 高：=高+ s [i]

• （1ずつ高くします）

• 低<高、実行-

  • 中：=低+（高-低+ 1）/ 2

  • ok（s、k + 1、mid）が真の場合、-

    • 低：=中

  • それ以外の場合

    • 高：=中-1

• ローに戻る

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool ok(vector <int> v, int cuts, int maxVal){
      int counter = 0;
      int temp = 0;
      for (int i = 0; i <= v.size(); i++) {
         if (temp >= maxVal) {
            counter++;
            temp = 0;
         }
         if (i == v.size()) {
            break;
         }
         temp += v[i];
      }
      return counter >= cuts;
   }
   int maximizeSweetness(vector<int>& s, int k) {
      int maxa = -1;
      int n = s.size();
      int low = 0;
      int high = 0;
      for (int i = 0; i < n; i++) {
         low = min(low, s[i]);
         high += s[i];
      }
      high++;
      while (low < high) {
         int mid = low + (high - low + 1) / 2;
         if (ok(s, k + 1, mid))
            low = mid;
         else
            high = mid - 1;
      }
      return low;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,7,8,9};
   cout << (ob.maximizeSweetness(v, 5));
}

入力

{1,2,3,4,5,6,7,8,9}, 5

出力

6