মান লিখুন: আমাদের কাছে X এবং H অ্যারে দুটো আছে, দুটোই N উপাদান বিশিষ্ট। আর D এবং A সংখ্যা দুটো। একটি গল্পে একটি রূপালি শিয়াল Nটি মอน্স্টার 상대로 লড়ছে। মোন্স্টারগুলো সারিয়ে আছে, i-তম মোন্স্টারের কোঅর্ডিনেট X[i] এবং স্বাস্থ্য H[i]। শিয়াল বোম্বা ব্যবহার করে আক্রমণ করে। x লোকেশনে বোম্বা ফেললে x-D থেকে x+D পরিসরের সব মোন্স্টার ক্ষতিগ্রস্ত হবে, তাদের স্বাস্থ্য A কমানো হবে। সব মোন্স্টারর স্বাস্থ্য ০ হলে শিয়াল জিতবে। জেতার জন্য ন্যূনতম কত বোম্বা লাগবে তা বের করতে হবে।
উদাহরণ
যদি ইনপুট হয় D = 3; A = 2; X = [1, 5, 9]; H = [2, 4, 2], তবে আউটপুট হবে 2, কারণ প্রথম বোম্বা কোঅর্ডিনেট ৪-এ, নতুন স্বাস্থ্য [0, 2, 2], তারপর ৬-এ বোম্বা ফেললে সব ০ হয়ে যাবে।
সমাধানের ধাপসমূহ
q বড় অ্যারে
x, h পেয়ার অ্যারে
n := X এর আকার
d := D, a := A
for i := 1 থেকে n:
num[i].x := X[i-1], num[i].h := H[i-1]
num সর্ট করুন
sum := 0
for i := 1 থেকে n:
q[i] += q[i-1]
num[i].h -= q[i] * a
যদি num[i].h <= 0: continue
p := (num[i].h % a == 0 ? num[i].h/a : num[i].h/a + 1)
tmp := num[i].x + 2*d
sum += p
q[i] += p
l := i, r := n
যতক্ষণ l < r:
mid := (l+r+1)/2
যদি num[mid].x <= tmp: l := mid
অন্যথায়: r := mid-1
q[l+1] -= p
sum রিটার্ন করুন
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 20;
int n, d, a, q[maxn];
struct node {
int x, h;
bool operator<(const node& a) const { return x < a.x; }
} num[maxn];
int solve(int D, int A, vector<int> X, vector<int> H) {
n = X.size(); d = D; a = A;
for (int i = 1; i <= n; i++) {
num[i].x = X[i - 1]; num[i].h = H[i - 1];
}
sort(num + 1, num + n + 1);
int sum = 0;
for (int i = 1; i <= n; i++) {
q[i] += q[i - 1];
num[i].h -= q[i] * a;
if (num[i].h <= 0) continue;
int p = (num[i].h % a == 0 ? num[i].h / a : num[i].h / a + 1);
int tmp = num[i].x + 2 * d;
sum += p;
q[i] += p;
int l = i, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (num[mid].x <= tmp) l = mid;
else r = mid - 1;
}
q[l + 1] -= p;
}
return sum;
}
int main() {
int D = 3, A = 2;
vector<int> X = { 1, 5, 9 }, H = { 2, 4, 2 };
cout << solve(D, A, X, H) << endl;
}
ইনপুট
3, 2, { 1, 5, 9 }, { 2, 4, 2 }
আউটপুট
2
