C++에서 초콜릿 나누기

<시간/>

몇 개의 덩어리로 구성된 초콜릿 바가 하나 있다고 가정합니다. 각 청크에는 단맛이라는 목록에 의해 주어진 고유한 단맛이 있습니다. K 친구와 초콜릿을 공유하려면 K 컷을 사용하여 초콜릿 바를 K+1 조각으로 자르기 시작합니다. 이제 각 조각은 연속적인 덩어리로 구성됩니다. 우리가 최소한의 총 단맛을 가진 조각을 꺼내고 다른 조각을 우리 친구들에게 준다면. 우리는 초콜릿 바를 최적으로 절단하여 얻을 수 있는 조각의 최대 총 단맛을 찾아야 합니다.

따라서 입력이 sweet =[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
initialize i :=0의 경우, i <=v의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
- temp> =maxVal이면
  - (카운터 1 증가)
  - 온도 :=0
- i가 v의 크기와 같으면 -
  - 루프에서 나오세요
- 온도 :=온도 + v[i]
카운터>=컷
일 때 true를 반환합니다.
기본 방법에서 다음을 수행합니다.
최대 :=-1
n :=s
의 크기
낮음 :=0, 높음 :=0
initialize 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