# UVA - 10382 Watering Grass （区间覆盖 贪心）

xiaoxiao2021-02-28  6

#include<iostream> #include<stdio.h> #include<algorithm> #include<cmath> using namespace std; struct line{ double lef, rig; }; int n; double w, l; line li[10000+10]; void f(int cnt, double o, double r){ double tmp = sqrt(r*r-((w*1.0/2.0)*(w*1.0/2.0))); li[cnt].lef = o-tmp; li[cnt].rig = o+tmp; } bool cmp(line a, line b) { return a.lef < b.lef; } int main() { while (scanf("%d%lf%lf", &n, &l, &w) != EOF){ int cnt = 0; for (int i = 0; i < n; i++) { double o, r; scanf("%lf%lf", &o, &r); if (2*r < w) continue; f(cnt++, o, r); } sort(li, li+cnt, cmp); int num = 0; double left = 0, right = 0; bool flag = false; if (li[0].lef <= 0) { int cur = 0; while (cur < cnt) { int i; for (i = cur; i < cnt && li[i].lef <= left; i++) if (li[i].rig > right) right = li[i].rig; if (i == cur) break; num++; left = right; cur = i; if (left >= l) { flag = true; break; } } } if (flag) printf("%d\n", num); else printf("-1\n"); } return 0; }

double 和 int 转换这里 WA 了，贪心时左端的判断放在循环里面导致 TLE，应该作为循环条件判断的。emm..太久没写题