โปรแกรม C++ หาจำนวนบอมบ์น้อยที่สุดฆ่ามอนสเตอร์ทั้งหมด

คำอธิบายปัญหา

สมมติว่าเรามีอาร์เรย์ X และ H ทั้งคู่ N องค์ประกอบ และตัวเลข D, A มีเรื่องราวว่าสุนัขจิ้งจอกเงินต่อสู้กับ N มอนสเตอร์ มอนสเตอร์ยืนแถว พิกัดตัวที่ i คือ X[i] พลังชีวิต H[i] สุนัขจิ้งจอกใช้บอมบ์ โยนที่พิกัด x จะทำลายมอนสเตอร์ในช่วง x-D ถึง x+D พลังชีวิตลดลง A เมื่อมอนสเตอร์ทุกตัวพลังชีวิต 0 สุนัขจิ้งจอกชนะ ต้องการหาจำนวนบอมบ์น้อยที่สุด

ตัวอย่าง: D = 3; A = 2; X = [1, 5, 9]; H = [2, 4, 2] ผลลัพธ์คือ 2 เพราะบอมบ์แรกที่พิกัด 4 พลังชีวิตกลายเป็น [0, 2, 2] บอมบ์ที่ 2 ที่พิกัด 6 ทำให้ [0, 0, 0]

ขั้นตอนการแก้ปัญหา

กำหนดอาร์เรย์ q ใหญ่
กำหนดอาร์เรย์คู่ x และ h
n := ขนาดของ X
d := D, a := A
สำหรับ i := 1 ถึง n:
    num[i].x := X[i-1]
    num[i].h := H[i-1]
เรียงลำดับ num
sum := 0
สำหรับ i := 1 ถึง n:
    q[i] := q[i] + q[i-1]
    num[i].h := num[i].h - q[i] * a
    ถ้า num[i].h <= 0: ข้าม
    p := (ถ้า num[i].h mod a == 0 แล้ว num[i].h / a มิฉะนั้น num[i].h / a + 1)
    tmp := num[i].x + 2 * d
    sum := sum + p
    q[i] := q[i] + p
    l := i, r = n
    while 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;
int 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;
    int A = 2;
    vector<int> X = { 1, 5, 9 };
    vector<int> H = { 2, 4, 2 };
    cout << solve(D, A, X, H) << endl;
}

อินพุต

3, 2, { 1, 5, 9 }, { 2, 4, 2 }

เอาต์พุต

2