จำนวนก๊อกขั้นต่ำในการเปิดรดน้ำสวนใน C++

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

เราต้องหาจำนวนก๊อกขั้นต่ำที่ควรเปิดให้รดน้ำทั้งสวน หากไม่มีวิธีแก้ปัญหาก็ให้คืนค่า -1

ดังนั้นหากอินพุตเป็น n =5 และ ranges =[3,4,1,1,1,0] เอาต์พุตจะเป็น 1 เนื่องจากจากการแตะครั้งที่สองจะครอบคลุมทั้งพื้น [-3 ถึง 5].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดขนาดอาร์เรย์ v (n + 1) และเติมด้วย -1

• สำหรับการเริ่มต้น i :=0 เมื่อ i <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • u :=สูงสุดของ i - ranges[i] และ 0

  • e :=ขั้นต่ำของ n และ i + ranges[i]

  • v[u] :=สูงสุดของ v[u] และ e

• ถ้า v[0] เหมือนกับ -1 แล้ว −

  • กลับ -1

• สกุลเงิน :=v[0]

• ผม :=0, ต่อไป :=0

• ในขณะที่ curr

  • ในขณะที่ฉัน <=curr ทำ -

    • next :=สูงสุดของ next และ v[i]

    • (เพิ่ม i ขึ้น 1)

  • ถ้า next เหมือนกับ curr แล้ว −

    • กลับ -1

  • curr :=ต่อไป

  • (เพิ่มการถอยกลับโดย 1)

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minTaps(int n, vector<int>& ranges) {
      int ret = 1;
      vector<int> v(n + 1, -1);
      for (int i = 0; i <= n; i++) {
         int u = max(i - ranges[i], 0);
         int e = min(n, i + ranges[i]);
         v[u] = max(v[u], e);
      }
      if (v[0] == -1)
      return -1;
      int curr = v[0];
      int i = 0;
      int next = 0;
      while (curr < n) {
         while (i <= curr) {
            next = max(next, v[i]);
            i++;
         }
         if (next == curr)
         return -1;
         curr = next;
         ret++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,4,1,1,1,0};
   cout << (ob.minTaps(5, v));
}

อินพุต

5, {3,4,1,1,1,0}

ผลลัพธ์

1