Cho mảng tọa độ X và máu H của N quái. Bom tại x gây sát thương A cho quái trong [x-D, x+D]. Tìm số bom tối thiểu để hết máu.
Ví dụ
Với D=3, A=2, X=[1,5,9], H=[2,4,2], đầu ra 2. Bom tại 4 (máu [0,2,2]), sau đó tại 6 (máu [0,0,0]).
Giải thuật
Sắp xếp quái theo tọa độ. Duyệt từ trái sang phải, dùng mảng chênh lệch q (difference array) để theo dõi sát thương tích lũy. Tại quái i, tính máu còn lại sau sát thương hiện tại. Nếu >0, tính số bom p cần, đặt bom tại X[i]+2D (xa nhất vẫn đánh trúng quái i), cập nhật q cho phạm vi ảnh hưởng.
Mã 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& o) const { return x < o.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;
}
Đầu vào / Đầu ra
Input: 3, 2, { 1, 5, 9 }, { 2, 4, 2 }
Output: 2