ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যার নাম nums এবং আরেকটি মান k। আমরা তালিকাটিকে k অ-খালি সাবলিস্টে বিভক্ত করতে পারি। আমাদের k সাবলিস্টের সর্বনিম্ন বৃহত্তম যোগফল খুঁজে বের করতে হবে।
সুতরাং, ইনপুট যদি nums =[2, 4, 3, 5, 12] k =2 এর মত হয়, তাহলে আউটপুট হবে 14, যেমন আমরা তালিকাকে বিভক্ত করতে পারি যেমন:[2, 4, 3, 5] এবং [ 12]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন সংজ্ঞায়িত করুন ok(), এটি অ্যারে v, k, x,
নেবে -
cnt :=0, যোগফল :=0
-
প্রতিটি উপাদানের জন্য i −
-
যদি যোগফল + i> x হয়, তাহলে −
-
যোগফল :=i
-
(1 দ্বারা cnt বাড়ান)
-
-
অন্যথায়
-
যোগফল :=যোগফল + i
-
-
-
cnt <=k, অন্যথা মিথ্যা
হলে true ফেরত দিন -
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
নিম্ন :=0, ret :=0, উচ্চ :=0
-
প্রতিটি উপাদানের জন্য i সংখ্যায়
-
উচ্চ :=উচ্চ + i
-
ret :=ret + i
-
low :=সর্বাধিক কম এবং i
-
-
যখন কম <=উচ্চ, করুন −
-
মধ্য :=নিম্ন + (উচ্চ - নিম্ন) / 2
-
যদি ok(সংখ্যা, k - 1, mid) সত্য হয়, তাহলে −
-
ret :=মধ্য
-
উচ্চ :=মধ্য - 1
-
-
অন্যথায়
-
নিম্ন :=মধ্য + 1
-
-
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
bool ok(vector <int>& v, int k, int x){
int cnt = 0;
int sum = 0;
for(int i : v){
if(sum + i > x){
sum = i;
cnt++;
}
else{
sum += i;
}
}
return cnt <= k;
}
int solve(vector<int>& nums, int k) {
int low = 0;
int ret = 0;
int high = 0;
for(int i : nums){
high += i;
ret += i;
low = max(low, i);
}
while(low <= high){
int mid = low + ( high - low) / 2;
if(ok(nums, k - 1, mid)){
ret = mid;
high = mid - 1;
}
else{
low = mid + 1;
}
}
return ret;
}
int main(){
vector<int> v = {2, 4, 3, 5, 12};
int k = 2;
cout << solve(v, k);
} ইনপুট
{2, 4, 3, 5, 12}, 2 আউটপুট
14
