ধরুন একটি মিষ্টির দোকান আছে যেখানে N বিভিন্ন ধরনের ক্যান্ডি পাওয়া যায় এবং সমস্ত N বিভিন্ন ধরনের ক্যান্ডির দাম দেওয়া আছে। দোকানটি একটি আকর্ষণীয় অফারও প্রদান করে। এই অফার অনুযায়ী, আমরা দোকান থেকে একটি একক ক্যান্ডি কিনতে পারি এবং বিনামূল্যে সর্বাধিক K বিভিন্ন ধরনের অন্যান্য ক্যান্ডি পেতে পারি। সমস্ত এন বিভিন্ন ধরণের ক্যান্ডি কিনতে আমাদের সর্বনিম্ন পরিমাণ অর্থ ব্যয় করতে হবে তা খুঁজে বের করতে হবে। সমস্ত এন বিভিন্ন ধরণের ক্যান্ডি কিনতে আমাদের সর্বাধিক পরিমাণ অর্থ ব্যয় করতে হবে। উভয় ক্ষেত্রেই আমাদের অবশ্যই অফারটি ব্যবহার করতে হবে এবং সর্বাধিক সম্ভাব্য ক্যান্ডি ফেরত পেতে হবে। যদি k বা তার বেশি ক্যান্ডি পাওয়া যায়, তাহলে প্রতিটি মিছরি কেনার জন্য আমাদের অবশ্যই k ক্যান্ডি নির্বাচন করতে হবে। কিন্তু, যদি k-এর কম ক্যান্ডি পাওয়া যায়, তাহলে আমাদের অবশ্যই মিছরি কেনার জন্য সব ক্যান্ডি নির্বাচন করতে হবে।
সুতরাং, ইনপুট যদি দাম =[4, 3, 2, 5] এবং k =2 এর মত হয়, তাহলে আউটপুট হবে সর্বনিম্ন =5 এবং সর্বোচ্চ =9। এর কারণ হল যখন k 2 হয়, যদি আমরা একটি ক্যান্ডি কিনি এবং আমরা বিনামূল্যে সর্বোচ্চ দুইটি নিতে পারি। প্রথম ক্ষেত্রে আমরা 2 মূল্যের ক্যান্ডি কিনতে পারি এবং 4 এবং 5 মূল্যের ক্যান্ডি বিনামূল্যে নিতে পারি, এছাড়াও আমরা 3 মূল্যের ক্যান্ডিও কিনতে পারি, তাই সর্বনিম্ন মূল্য =2 + 3 =5। অন্যদিকে, দ্বিতীয়টিতে আমরা 5 টাকা দামের ক্যান্ডি কিনি এবং 2 এবং 3 মূল্যের ক্যান্ডি বিনামূল্যে নিতে পারি, অথবা আমরা 4 মূল্যের ক্যান্ডিও কিনতে পারি। সুতরাং, সর্বোচ্চ খরচ =4 + 5 =9।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন get_min() সংজ্ঞায়িত করুন। এটি A,k
লাগবে -
n :=A
এর আকার -
তালিকা A
সাজান -
res :=0, i:=0
-
যখন n অ-শূন্য, কর
-
res :=res + A[i]
-
n :=n-k
-
i :=i + 1
-
-
রিটার্ন রিটার্ন
-
একটি ফাংশন সংজ্ঞায়িত করুন get_max()। এটি A, k
লাগবে -
n :=A
এর আকার -
তালিকা A
সাজান -
res :=0, idx :=0
-
i:=n-1
-
যখন i>=idx, করবেন
-
res :=res + A[i]
-
idx :=idx + k
-
i :=i - 1
-
-
রিটার্ন রিটার্ন
-
মূল পদ্ধতি থেকে ফলাফল পেতে এই দুটি ফাংশন কল করুন
-
get_min(A, k)
-
get_max(A, k)
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def get_min(A,k): n = len(A) A.sort() res = 0 i=0 while(n): res += A[i] n = n-k i += 1 return res def get_max(A, k): n = len(A) A.sort() res = 0 idx = 0 i=n-1 while(i>=idx): res += A[i] idx += k i -= 1 return res A = [4, 3, 2, 5] k = 2 print(get_min(A, k),get_max(A, k))
ইনপুট
[4, 3, 2, 5], 2
আউটপুট
5 9
