当前位置: 代码迷 >> 综合 >> UVA 10382 Watering Grass 区间覆盖问题 -
  详细解决方案

UVA 10382 Watering Grass 区间覆盖问题 -

热度:55   发布时间:2023-09-23 05:20:06.0

题目地址:http://vjudge.net/problem/UVA-10382

第一想法:

1)ri*2<=w的去掉

2)肯定为了让决策有序化,按p排序

3)很明显 ,状态两种:开与不开,而且位置固定的,那么就可以看成由n个区间,求能覆盖整个区间的最小数量,那不是就贪心的区间覆盖问题嘛


思路来自,刘汝佳的区间覆盖:

1)预处理[a,b] 按照a的大小排列

2)从L点出发,把L左边的所有区间全部忽略

3)在从L点出发的区间里选一个最长的,R ,赋值L=R,如果没有L点出发的,表示无解

4)如果L<终点,继续2),否则返回,完成任务


#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
struct Aug
{double x1,x2;bool operator < (const Aug& p) const {return x1<p.x1;}
}A[10000+10];int main(int argc, char const *argv[])
{int n;double l,w;while(scanf("%d%lf%lf",&n,&l,&w)==3){int cnt=0; double p,r;REP(i,1,n){scanf("%lf%lf",&p,&r);if(r*2<=w) continue;double s=sqrt(r*r-w*w/4);A[cnt++]=Aug{p-s,p+s};}sort(A,A+cnt);double L=0.0; int pos=0,ans=0;for(;;){REP(i,pos,cnt-1)   //以L为起点,所以去掉L左边的所有区间if(L>=A[i].x1) A[i].x1=L;else break;double R=0.0;  //在起点为L的中选个最长的if(pos<cnt&&L==A[pos].x1) while(pos<cnt&&L==A[pos].x1) R=max(R,A[pos].x2),pos++;else break;     //没有起点为L的表明无法完全覆盖if(R==0||L>=l) break; //已达终点就及时退出L=R; ans++;}printf("%d\n", L>=l?ans:-1);}return 0;
}