首页 > 代码库 > UVA10382- Watering Grass(区间覆盖问题)
UVA10382- Watering Grass(区间覆盖问题)
题意:一块长l,宽w的长方形草坪,在其中心线的不同位置处装有n个点状的喷水装置。每个喷水装置i可将以它为中心,半径为ri的圆形区域润湿。请选择尽量少的喷水装置,把整个草坪全部润湿。
思路:变形的区间覆盖问题。其实我们只要将圆形转化为覆盖在草坪上的矩形即可。当半径ri<w/2时,圆形面积在草坪真正有用的只是一条竖线,对于完全覆盖草坪没有任何意义,所以这种喷水装置不取。转化完之后,只要按照区间覆盖问题去解决就行了。先判断是否能从开头开始覆盖,之后每次取起点相同,但是区间长度最长的那个区间(期间注意判断是否能覆盖每一个地方)。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int MAXN = 10005; struct node{ double s, e; }t[MAXN]; int n; double l, w; int cmp(node a, node b) { if (a.s != b.s) return a.s < b.s; else return a.e > b.e; } int main() { while (scanf("%d%lf%lf", &n, &l, &w) != EOF) { int cnt = 0; for (int i = 0; i < n; i++) { double p, r; scanf("%lf%lf", &p, &r); if (r > w / 2) { double temp = sqrt(r * r - w * w / 4); t[cnt].s = p - temp; t[cnt].e = p + temp; cnt++; } } sort(t, t + cnt, cmp); int num = 0, flag = 0; double start = 0, end = 0; if (t[0].s <= 0) { int left = 0; while (left < cnt) { int right = left; while (right < cnt && t[right].s <= start) { if (t[right].e >= end) end = t[right].e; right++; } if (right == left) { break; } num++; left = right; start = end; if (start >= l) { flag = 1; break; } } } if (flag) printf("%d\n", num); else printf("-1\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。