Số lượng vòi tối thiểu để mở để tưới vườn trong C ++

Giả sử có một khu vườn một chiều trên trục x. Vị trí bắt đầu của khu vườn là 0 và vị trí kết thúc là n. Có n + 1 vòi đặt tại các điểm [0, 1, ..., n] trong vườn. Nếu chúng ta có một số nguyên n và một dãy số nguyên có độ dài n + 1 trong đó dãy [i] là vòi thứ i có thể tưới vùng [i - dãy [i], i + dãy [i]] khi vùng đó mở.

Ta phải tìm số vòi tối thiểu phải mở để tưới cả vườn, nếu không có giải pháp nào thì trả về -1.

Vì vậy, nếu đầu vào là n =5 và dãy =[3,4,1,1,1,0], thì đầu ra sẽ là 1, vì từ lần nhấn thứ hai, nó sẽ bao phủ toàn bộ mặt bằng [-3 đến 5].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một mảng v có kích thước (n + 1) và điền vào giá trị này bằng -1

• để khởi tạo i:=0, khi i <=n, cập nhật (tăng i lên 1), thực hiện -

  • u:=tối đa trong số i - phạm vi [i] và 0

  • e:=tối thiểu của n và i + phạm vi [i]

  • v [u]:=tối đa là v [u] và e

• nếu v [0] giống -1, thì -

  • trả về -1

• curr:=v [0]

• i:=0, tiếp theo:=0

• trong khi curr

  • trong khi tôi <=curr, do -

    • next:=tối đa của tiếp theo và v [i]

    • (tăng tôi lên 1)

  • nếu tiếp theo giống với curr, thì -

    • trả về -1

  • curr:=tiếp theo

  • (tăng ret lên 1)

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Đầu ra

1