C++ তে চকোলেট ভাগ করুন

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

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

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সংজ্ঞায়িত করুন ঠিক আছে(), এটি একটি অ্যারে v, কাটস, maxVal,

  নেবে

• কাউন্টার :=0, তাপমাত্রা :=0

• আরম্ভ করার জন্য i :=0, যখন i <=v এর আকার, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

  • যদি temp> =maxVal, তারপর

    • (1 দ্বারা কাউন্টার বাড়ান)

    • তাপমাত্রা :=0

  • যদি আমি v এর আকারের সমান হয়, তাহলে −

    • লুপ থেকে বেরিয়ে আসুন

  • temp :=temp + v[i]

• কাউন্টার>=কাট

  হলে সত্য ফেরত দিন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:

• ম্যাক্সা :=-1

• n :=s

  এর আকার

• নিম্ন :=0, উচ্চ :=0

• আরম্ভ করার জন্য i :=0, যখন i

  • নিম্ন :=সর্বনিম্ন নিম্ন এবং 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