Số vòi nước tối thiểu để tưới vườn trong C++

Có vườn 1D trên trục x từ 0 đến n. Có n+1 vòi tại [0,1,...,n]. Vòi i tưới vùng [i-ranges[i], i+ranges[i]]. Tìm số vòi tối thiểu để tưới hết vườn, trả về -1 nếu không thể.

Ví dụ: n=5, ranges=[3,4,1,1,1,0], đầu ra=1. Vòi thứ 2 (chỉ số 1) tưới [-3,5] bao phủ cả vườn.

Giải pháp

Chuyển thành bài toán chọn đoạn bao phủ [0,n] với số đoạn tối thiểu (greedy):

• Tạo mảng v[n+1] = -1, v[u] = max(v[u], e) với u=max(0,i-ranges[i]), e=min(n,i+ranges[i])
• Nếu v[0]==-1: trả về -1 (không bao phủ được điểm 0)
• curr = v[0], i=0, next=0, ret=1
• While curr < n:
  • While i ≤ curr: next = max(next, v[i]), i++
  • Nếu next == curr: trả về -1 (không mở rộng được)
  • curr = next, ret++
• Trả về ret

Ví dụ mã C++

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

int main() { 
    Solution ob; 
    vector<int> v = {3,4,1,1,1,0}; 
    cout << (ob.minTaps(5, v)); 
    return 0; 
}

Đầu vào

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

Đầu ra

1