মান লিজিয়ে, একটি টেলিকম অপারেটর "all-in-one" নামক একটি সেবা চালু করেছে যা n টি ওটিটি কন্টেন্ট প্রোভাইডারের এক্সেস দেয় একটি নির্দিষ্ট দাম k ডলারে। এখন যদি আমরা সরাসরি ওটিটি প্ল্যাটফর্মগুলো সাবস্ক্রাইব করতে চাই, তবে প্রতিটি প্ল্যাটফর্মের জন্য আলাদা ফি দিতে হয়। আমাদের সব মাসে সব প্ল্যাটফর্মের সাবস্ক্রিপশন দরকার নয়, তাই আমাদের খরচ-কার্যকর উপায় খুঁজে বের করতে হবে। প্ল্যাটফর্ম i-র সেবা দরকার থাকবে start_month[i] মাস থেকে এবং শেষ হবে end_month[i] মাসে। প্ল্যাটফর্ম i-র সাবস্ক্রিপশন ফি price[i]। আমাদের লক্ষ্য হলো আমাদের প্রয়োজন অনুযায়ী সব প্ল্যাটফর্ম সাবস্ক্রাইব করার জন্য ন্যূনতম কত টাকা খরচ হবে তা বের করা।
যেমন, ইনপুট হলে n = 3, k = 10, start_month = {1, 2, 1}, end_month = {3, 3, 2}, price = {5, 7, 8}, তবে আউটপুট হবে 30।
আমাদের ৩ মাস পর্যায় সেবা দরকার।
প্রথম মাসে প্ল্যাটফর্ম ১ এবং ৩ দরকার। আলাদা করলে খরচ ৫ + ৮ = ১৩ ডলার, কিন্তু "all-in-one" প্যাকেজ দিয়ে ১০ ডলারেই হবে। দ্বিতীয় মাসে তিনটি দরকার যা আলাদা করলে ২০ ডলার, কিন্তু প্যাকেজ দিয়ে ১০ ডলার। তৃতীয় মাসে মোট খরচ ১২ ডলার, কিন্তু প্যাকেজ দিয়ে ১০ ডলার।
তাই মোট খরচ = ১০ + ১০ + ১০ = ৩০।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
pairArray অ্যারে সংজ্ঞায়িত করুন i := 0 থেকে n-1 পর্যন্ত: pairArray-র শেষে pair(start_month[i], price[i]) যোগ করুন pairArray-র শেষে pair(end_month[i] + 1, -price[i]) যোগ করুন pairArray সোর্ট করুন pre := 0 c := 0 res := 0 pairArray-র প্রতিটি p উপাদানের জন্য: day := p.first - pre res := res + min(k, c) * day c := c + p.second pre := p.first return res
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; vector<vector<int>> G; vector<int> res; int solve(int n, int k, int start_month[], int end_month[], int price[]){ vector<pair<int, int>> pairArray; for(int i = 0; i < n; i++) { pairArray.push_back(make_pair(start_month[i], price[i])); pairArray.push_back(make_pair(end_month[i] + 1, -price[i])); } sort(pairArray.begin(), pairArray.end()); int pre = 0; int c = 0; int res = 0; for(auto p : pairArray) { int day = p.first - pre; res += min(k, c) * day; c += p.second; pre = p.first; } return res; } int main() { int n = 3, k = 10, start_month[] = {1, 2, 1}, end_month[] = {3, 3, 2}, price[] = {5, 7, 8}; cout<< solve(n, k, start_month, end_month, price); return 0; } ইনপুট
3, 10, {1, 2, 1}, {3, 3, 2}, {5, 7, 8} আউটপুট
30
