1326. 灌溉花园的最少水龙头数目


图片说明
图片说明
图片说明


同 codeforces 1175 E. Minimal Segment Cover

class Solution {
public:
    int minTaps(int n, vector<int>& a) {
        int L[n+5]={0};
        for(int i=0,l;i<=n;i++)l=max(0,i-a[i]),L[l]=max(L[l],min(n,i+a[i]));
        for(int i=1;i<=n;i++)L[i]=max(L[i-1],L[i]);
        int ans=0;
        for(int i=0;i<n;i=L[i],ans++)if(L[i]==i)return -1;
        return ans;
    }
};