ধরুন, আমরা একটি ভিডিও গেম খেলছি যেখানে নায়ক তার শত্রুদের পরাস্ত করতে ছুরি ব্যবহার করে। নায়ক শত্রুকে কাটার জন্য ছুরি ব্যবহার করতে পারে বা শত্রুর দিকে ছুঁড়তে পারে। যদি নায়ক একটি ছুরি ছুঁড়ে ফেলে, তবে তা আর উদ্ধার করা যাবে না। ছুরি i দ্বারা মোকাবেলা করা ক্ষতি অ্যারে 'ছুরি'-তে দেওয়া হয়েছে যেখানে প্রতিটি উপাদান {স্ল্যাশ, থ্রো} আকারের। 'স্ল্যাশ' মানে সেই ছুরি দিয়ে শত্রুর ক্ষয়ক্ষতি এবং 'থ্রো' মানে সেই বিশেষ ছুরি নিক্ষেপের মাধ্যমে তাদের ক্ষতি করা। স্ল্যাশিং সীমাহীন বার করা যেতে পারে, কিন্তু একটি ছুরি শুধুমাত্র একবার নিক্ষেপ করা যেতে পারে। এখন, একজন শত্রু দেখা যাচ্ছে যার স্বাস্থ্য আছে। শত্রুকে পরাস্ত করার জন্য আমাদের ন্যূনতম সংখ্যক অপারেশন (স্ল্যাশিং বা নিক্ষেপ) খুঁজে বের করতে হবে। শত্রু পরাজিত হয় যখন তাদের 0 স্বাস্থ্য থাকে।
সুতরাং, যদি ইনপুট হয় n =2, h =11, knives ={{4, 5}, {3, 6}}, তাহলে আউটপুট হবে 2।
যদি নায়ক উভয় ছুরি ছুড়ে ফেলে, তাহলে ক্ষতি হয় 5 + 6 =11। শত্রুর স্বাস্থ্য 0 হয়ে যায়, তাই তারা পরাজিত হয়।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
val := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
val := maximum of (val and first value of knives[i])
sort the array knives
res := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
if second value of knives[i] > val, then:
h := h - second value of knives[i]
(increase res by 1)
if h <= 0, then:
print(res)
exit
Otherwise
Come out from the loop
print((res + ceiling value of (h / (double)))) উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
void solve(int n, int h, vector<pair<int, int>> knives){
int val = 0;
for(int i = 0; i < n; i++){
val = max(val, knives[i].first);
}
sort(knives.begin(), knives.end());
int res = 0;
for(int i = 0; i < n; i++){
if(knives[i].second > val){
h -= knives[i].second;
res++;
if(h <= 0){
cout << res << endl;
return;
}
}
else break;
}
cout << (res + ceil(h / (double)val)) << endl;
}
int main() {
int n = 2, h = 11;
vector<pair<int, int>> knives = {{4, 5}, {3, 6}};
solve(n, h, knives);
return 0;
} ইনপুট
2, 11, {{4, 5}, {3, 6}} আউটপুট
2
