Chia sô cô la trong C ++

Giả sử chúng ta có một thanh sô cô la bao gồm một số khối. Trong mỗi đoạn, nó có vị ngọt riêng được đưa ra bởi một danh sách gọi là độ ngọt. Nếu chúng ta muốn chia sẻ sô cô la cho K bạn bè, vì vậy chúng tôi bắt đầu cắt thanh sô cô la thành K + 1 miếng bằng cách sử dụng K vết cắt, bây giờ mỗi miếng bao gồm một số khối liên tiếp. Nếu chúng ta lấy ra một miếng với tổng độ ngọt tối thiểu và đưa những miếng khác cho bạn bè của chúng ta. Chúng ta phải tìm ra tổng độ ngọt tối đa của miếng mà chúng ta có thể nhận được bằng cách cắt thanh sô cô la một cách tối ưu.

Vì vậy, nếu đầu vào là độ ngọt =[1,2,3,4,5,6,7,8,9], K =5, thì đầu ra sẽ là 6 vì Bạn có thể chia sô cô la cho [1,2 , 3], [4,5], [6], [7], [8], [9] những phần này.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm ok (), điều này sẽ lấy một mảng v, vết cắt, maxVal,
bộ đếm:=0, tạm thời:=0
để khởi tạo i:=0, khi i <=size of v, hãy cập nhật (tăng i lên 1), thực hiện -
- nếu temp> =maxVal, thì
  - (tăng bộ đếm lên 1)
  - tạm thời:=0
- nếu tôi giống với kích thước của v, thì -
  - Ra khỏi vòng lặp
- temp:=temp + v [i]
trả về true khi bộ đếm> =cắt
Từ phương thức chính, thực hiện như sau:
maxa:=-1
n:=kích thước của s
thấp:=0, cao:=0
để khởi tạo i:=0, khi i
- thấp:=tối thiểu của thấp và s [i]
- cao:=high + s [i]
(tăng cao 1)
trong khi thấp
- mid:=low + (high - low + 1) / 2
- nếu ok (s, k + 1, mid) là true thì -
  - thấp:=trung bình
- Nếu không
  - cao:=giữa - 1
trở lại mức thấp

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Chia sô cô la trong C ++

Ví dụ

Đầu vào

Đầu ra