সমস্যা বিবরণ
N আকারের একটি অ্যারে দেওয়া আছে যা বালতি (bucket) উপস্থাপন করে, প্রতিটি ইনডেক্সে আইটেমের সংখ্যা থাকে। Kটি টУারের মধ্যে সব আইটেম ডেলিভারি করতে হবে। এক টুরে শুধু একটি বালতি থেকে আইটেম নেওয়া যাবে। প্রতি টুরে ন্যূনতম কতগুলো আইটেম ডেলিভারি করতে হবে যাতে K টУারের মধ্যে সব আইটেম ডেলিভারি হয় তা বের করুন।
যদি ৫টি বালতিতে আইটেম = {1, 3, 5, 7, 9} এবং ১০টি টুর থাকে, তবে প্রতি টুরে ৩টি আইটেম ডেলিভারি করা যাবে:
- ১ম বালতি আকার ১, দরকার টুর = ১
- ২য় বালতি আকার ৩, দরকার টুর = ১
- ৩য় বালতি আকার ৫, দরকার টুর = ২ (৩ + ২ আইটেম)
- ৪র্থ বালতি আকার ৭, দরকার টুর = ৩ (৩ + ৩ + ১ আইটেম)
- ৫ম বালতি আকার ৯, দরকার টুর = ৩ (৩ + ৩ + ৩ আইটেম)
মোট টুর = ১০
এলগরিদম
1. প্রতি ডেলিভারিতে ন্যূনতম আইটেম বিতরণ বের করুন 2. ১ থেকে বালতিতে সর্বোচ্চ আইটেম মান পর্যন্ত ইটারেট করুন এবং প্রতিটি বালতির জন্য দরকার টুর গণনা করুন 3. যেটি প্রথম K-এর চেয়ে কম বা সমান টур দেবে, সেটিই চাহিদা
উদাহরণ কোড
#include <iostream>
#include <climits>
#include <cmath>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int minItemsDeliveried(int *arr, int n, int k) {
int maxElement = INT_MIN;
for (int i = 0; i < n; ++i) {
maxElement = max(maxElement, arr[i]);
}
for (int i = 1; i < maxElement + 1; ++i) {
int tours = 0;
for (int j = 0; j < n; ++j) {
if (arr[j] % i == 0) {
tours += arr[j] / i;
} else {
tours += floor(arr[j] / i) + 1;
}
}
if (tours <= k) {
return i;
}
}
return 1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int k = 10;
cout << "Minimum items to be delivered = " << minItemsDeliveried(arr, SIZE(arr), k) << endl;
return 0;
}
আউটপুট
প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:
Minimum items to be delivered = 3
