leetcode：1326. 灌溉花园的最少水龙头数目（dp，困难）

题目：

分析：直接把水龙头转化为区间，那么就是一道简答的区间问题。

要全部覆盖，那么显然要选择某一位置开头（或包含某一位置），然后可以向右达到的最大长度。

也就是一道穿着华丽外表的基础题。

代码：

class Solution { public: struct node{ int x; int y; } nn[10005]; int n2=0; static bool cmp(struct node &n1,struct node &n2) { if(n1.x==n2.x) return n1.y<n2.y; return n1.x<n2.x; } int minTaps(int n, vector<int>& r) { //int n; //vector<int> r; for(int i=0;i<r.size();i++) { if(r[i]==0) continue; nn[n2].x=max(0,i-r[i]); nn[n2].y=min(n,i+r[i]); n2++; } sort(nn,nn+n2,cmp); int l=0; int ans=0; int n3=0; while(1) { if(l>=n) return ans; if(n2==n3) return -1; if(nn[n3].x>l) return -1; int maxx=nn[n3].y; n3++; while(n3<n2) {//找包含l且最大的。 if(nn[n3].x>l) break; maxx=max(nn[n3].y,maxx); n3++; } l=maxx; ans++; } } };