สมมติว่าเรามีอาร์เรย์ A ขนาด n องค์ประกอบเป็น 0 หรือ 1 มีต้นไม้ ใน n วันต่อเนื่อง ถ้า A[i] = 0 ไม่ได้รดน้ำ ถ้า 1 รดน้ำ ต้นไม้โตดังนี้:
- ไม่ได้รดน้ำ 2 วันติดตาย
- รดน้ำวันที่ i โต 1 ซม.
- รดน้ำวันที่ i และ i+1 ติดกัน โต 5 ซม. แทน 1 ซม.
- ไม่รดน้ำวันที่ i ไม่โต
เริ่มต้นต้นไม้สูง 1 ซม. หาความสูงหลัง n วัน ถ้าตายส่ง -1
เช่น ถ้าอินพุตคือ A = [0, 1, 1] เอาต์พุตจะเป็น 7 เพราะวันแรกไม่โต สูง 1 วันที่สองโตเป็น 2 วันที่สามโต 5 ซม. รวม 7
ขั้นตอนการแก้ปัญหา
r := 1
y := 0
n := ขนาดของ A
for i := 0 ถึง n-1:
x := A[i]
if r == -1: continue
if x และ y ทั้งคู่ non-zero: r := r + 5
else if x non-zero: เพิ่ม r ขึ้น 1
else if ไม่ x และ ไม่ y และ i > 0: r := -1
y := x
return r
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A) {
int r = 1;
int y = 0;
int n = A.size();
for (int i = 0; i < n; ++i) {
int x = A[i];
if (r == -1) continue;
if (x && y) r += 5;
else if (x) ++r;
else if (!x && !y && i > 0) r = -1;
y = x;
}
return r;
}
int main() {
vector<int> A = { 0, 1, 1 };
cout << solve(A) << endl;
}อินพุต
{ 0, 1, 1 }
เอาต์พุต
7
