สมมติเรามีอาร์เรย์ที่เก็บตัวเลขบวกและลบ อาร์เรย์นี้แทนจุดตรวจ (checkpoint) จากปลายหนึ่งไปอีกปลายหนึ่งของถนน ค่าบวกและลบแทนพลังงานที่จุดตรวจ ค่าบวกเพิ่มพลังงาน ค่าลบลดพลังงาน เราต้องหาระดับพลังงานเริ่มต้นเพื่อข้ามถนน ให้พลังงานไม่เป็น 0 หรือติดลบ
สมมติอาร์เรย์ A = {4, -6, 2, 3} ให้พลังงานเริ่มต้นเป็น 0 หลังจุดตรวจแรก พลังงานคือ 4 ไปจุดที่สอง พลังงาน = 4 + (-6) = -2 น้อยกว่า 0 ดังนั้นต้องเริ่มต้นด้วย 3 หลังจุดแรก 3+4=7 หลังจุดที่สอง 7+(-6)=1
อัลกอริทึม
minInitEnergy(arr, n): begin initEnergy := 0 currEnergy := 0 flag := false for i in range 0 to n, do currEnergy := currEnergy + arr[i] if currEnergy <= 0, then initEnergy := initEnergy + absolute value of currEnergy + 1 currEnergy := 1 flag := true end if done if flag is false, return 1, otherwise return initEnergy end
ตัวอย่าง
#include <iostream> #include <cmath> using namespace std; int minInitEnergy(int arr[], int n){ int initEnergy = 0; int currEnergy = 0; bool flag = false; for (int i = 0; i<n; i++){ currEnergy = currEnergy + arr[i]; if (currEnergy <= 0){ initEnergy = initEnergy + abs(currEnergy) + 1; currEnergy = 1; flag = true; } } if (flag == false) return 1; else return initEnergy; } int main() { int A[] = {4, -6, 2, 3}; int n = sizeof(A)/sizeof(A[0]); cout << "Minimum Energy: " << minInitEnergy(A, n); }ผลลัพธ์
Minimum Energy: 3
