সি++-এ চকলেট ভাগ করা

ধরা যাক একটি চকলেট বার আছে যেটির কিছু চাঙ্ক আছে। প্রতিটি চাঙ্কের নিজস্ব মিষ্টি স্তর আছে যেটি sweetness লিস্টে দেওয়া আছে। যদি আমরা চকলেটটি K বন্ধু중에 ভাগ করতে চাই তাই আমরা চকলেট বারটি K+1 টুকরোতে K কাট দিয়ে কাটব, এখন প্রতিটি টুকরোতে কিছু লগ্ন চাঙ্ক থাকবে। যদি আমরা ন্যূনতম মোট মিষ্টি স্তরের টুকরোটি বের করে দিই এবং বাকি টুকরোগুলো বন্ধুদের দিই। আমাদের চকলেট বারটি সর্বোত্তমভাবে কাটা দিয়ে আমরা যে সর্বোচ্চ মোট মিষ্টি স্তর পেতে পারি সেটি খুঁজে বের করতে হবে।

তাই, যদি ইনপুট sweetness = [1,2,3,4,5,6,7,8,9], K = 5 হয়, তবে আউটপুট হবে 6 কারণ আপনি চকলেটটিকে [1,2,3], [4,5], [6], [7], [8], [9] এই টুকরোগুলোতে ভাগ করতে পারেন।

এটি সমাধান করতে, আমরা নিচের ধাপগুলো অনুসরণ করব -

একটি ok() ফাংশন ডিফাইন করুন, এটি v, cuts, maxVal নেবে,
counter := 0, temp := 0
i := 0 থেকে শুরু করুন, যখন i <= v-এর আকার, (i ১ করে বাড়ান), করুন -
- যদি temp >= maxVal, তবে
  - (counter ১ করে বাড়ান)
  - temp := 0
- যদি i, v-এর আকারের সমান হয়, তবে -
  - লুপ থেকে বের হোন
- temp := temp + v[i]
counter >= cuts হলে true রিটার্ন করুন
মূল মেথড থেকে নিচের ধাপগুলো করুন:
maxa := -1
n := s-এর আকার
low := 0, high := 0
i := 0 থেকে শুরু করুন, যখন i < n, (i ১ করে বাড়ান), করুন -
- low := low এবং s[i]-এর মিনিমাম
- high := high + s[i]
(high ১ করে বাড়ান)
যখন low < high, করুন -
- mid := low + (high - low + 1) / 2
- যদি ok(s, k + 1, mid) true হয়, তবে -
  - low := mid
- অন্যথায়
  - high := mid - 1
low রিটার্ন করুন

বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন -

উদাহরণ

#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