คำนวณรังสีสุทธิของสถานีหลังกระจายรังสีซ้ำใน C++

มีสถานี N แห่งเรียงเป็นเส้นตรง แต่ละแห่งมีกำลังรังสี R เดิม กระจายรังสีให้เพื่อนบ้าน: ระยะ 1 เพิ่ม R-1, ระยะ 2 เพิ่ม R-2, ... จนกว่าจะเหลือ 0 หรือติดลบ

ตัวอย่าง: Arr = [1, 2, 3] → ผลลัพธ์ [3, 4, 4]

• Index 0: 1 + (2-1) + (3-2) = 3
• Index 1: 2 + (1-1) + (3-1) = 4
• Index 2: 3 + (2-1) = 4

อัลกอริทึม

สำหรับแต่ละสถานี i ที่มีกำลัง R: เพิ่มค่าให้เพื่อนบ้านซ้ายและขวา ทีละระยะ จนกว่าค่าที่เพิ่มจะ ≤ 0

ตัวอย่างโค้ด (แก้ไขจากต้นฉบับที่ผิด)

#include <iostream>
#include <vector>
using namespace std;

vector finalRadiation(vector& stations) {
    int n = stations.size();
    vector result = stations; // เริ่มจากค่าเดิม

    for (int i = 0; i < n; i++) {
        int R = stations[i];
        // กระจายไปซ้าย
        for (int d = 1; d <= R; d++) {
            int left = i - d;
            if (left < 0) break;
            int add = R - d;
            if (add <= 0) break;
            result[left] += add;
        }
        // กระจายไปขวา
        for (int d = 1; d <= R; d++) {
            int right = i + d;
            if (right >= n) break;
            int add = R - d;
            if (add <= 0) break;
            result[right] += add;
        }
    }
    return result;
}

int main() {
    vector stations = {1, 2, 3};
    vector result = finalRadiation(stations);

    cout << "Final radiation: ";
    for (int val : result)
        cout << val << " ";
    // Output: 3 4 4

    return 0;
}

ผลลัพธ์

Final radiation: 3 4 4

หมายเหตุ

โค้ดต้นฉบับคัดลอกมาจากปัญหา Petrol Pump (โจทย์ก่อนหน้า) ผิดพลาด เราเขียนใหม่ให้ตรงกับโจทย์จริง

ความซับซ้อน

เวลา: O(n × R_max) โดย R_max = ค่ารังสีสูงสุด สำหรับ R ใหญ่ ควรใช้ Difference Array / Prefix Sum เพื่อลดเป็น O(n)