এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া আছে আকার n এবং একটি সংখ্যা S। আমাদের কাজ হল মডিফাইড অ্যারেতে মিনিমাম ভ্যালুর ম্যাক্সিমাম পসিবল ভ্যালু বের করা।
অ্যারে মডিফাই করার নিয়ম:
মডিফিকেশনের আগে ও পরের অ্যারে উপাদানগুলোর যোগফলের পার্থক্য S হতে হবে।
মডিফাইড অ্যারেতে নেগেটিভ ভ্যালু অনুমোদিত নয়।
মডিফাইড অ্যারেতে, অ্যারেতে মিনিমাম ভ্যালুটাকে ম্যাক্সিমাইজ করতে হবে।
অ্যারে মডিফিকেশন করা যাবে অ্যারের যেকোনো উপাদান বড়ানো বা ছোট করে।
এই কন্সট্রেইন্ট ব্যবহার করে আমাদের নতুন অ্যারে বের করতে হবে এবং অ্যারেতে সবচেয়ে ছোট উপাদানের ম্যাক্সিমাইজড ভ্যালু রিটার্ন করতে হবে।
উদাহরণ
সমস্যাটি বুঝতে একটি উদাহরণ নিই:
ইনপুট : arr[] = {4, 5, 6} S = 2
আউটপুট : 4
ব্যাখ্যা
মডিফাইড অ্যারে হল {4, 5, 5}
সমাধানের পদ্ধতি
আমাদের মডিফাইড অ্যারেতে সবচেয়ে ছোট ভ্যালুটাকে ম্যাক্সিমাইজ করতে হবে। আমরা বাইনারি সার্চ ব্যবহার করে অপ্টিমাম ভ্যালু বের করব যা ০ (সর্বনিম্ন সম্ভাব্য) এবং arr_min (সর্বোচ্চ সম্ভাব্য) এর মাঝপথে। আমরা সবচেয়ে ছোট সম্ভাব্য ভ্যালুর জন্য পার্থক্য চেক করব।
কিছু বিশেষ শর্ত:
যদি S অ্যারে যোগফলের চেয়ে বড় হয়, কোনো সমাধান সম্ভব নয়।
যদি S অ্যারে যোগফলের সমান হয়, ০ হবে মিনিমাম উপাদানের ভ্যালু।
উদাহরণ প্রোগ্রাম
আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:
#include <iostream>
using namespace std;
int findmaximisedMin(int a[], int n, int S) {
int minVal = a[0];
int arrSum = a[0];
for (int i = 1; i < n; i++) {
arrSum += a[i];
minVal = min(a[i], minVal);
}
if (arrSum < S)
return -1;
if (arrSum == S)
return 0;
int s = 0;
int e = minVal;
int ans;
while (s <= e) {
int mid = (s + e) / 2;
if (arrSum - (mid * n) >= S) {
ans = mid;
s = mid + 1;
}
else
e = mid - 1;
}
return ans;
}
int main() {
int a[] = { 4, 5, 6 };
int S = 2;
int n = sizeof(a) / sizeof(a[0]);
cout << "The maximum value of minimum element of the modified array is " << findmaximisedMin(a, n, S);
return 0;
}
আউটপুট
The maximum value of minimum element of the modified array is 4
