UVA - 10382Watering Grass（贪心）

传送🚪

题意：8组数据，草坪长20，宽为2，下面8个喷水器，数据分别为横坐标和半径。问最少需要多少个喷水器可以覆盖整个草坪，如果不能完全覆盖草坪输出-1；

分析：

勾股定理，已知圆的半径和草坪的宽，可以求出该喷水器在草坪的左右最大值。求出left，right后，进入循环体，从小到大排序，while循环贪心即可，如果后面几个喷水器left在当前必安的喷水器的左边，就求出这几个右边的最大值，才用这个喷水器继续贪心，直到right大于等于草坪长度。

ac代码：

#include 
#include 
#include 
#include 
using namespace std;
int n,l,w;
struct node
{double left,right;
}wt[10010];
int cmp(node a,node b)
{return a.left<b.left;
}
int main()
{while(~scanf("%d%d%d",&n,&l,&w)){double p,r;int cnt=0;for(int i=1;i<=n;i++){scanf("%lf%lf",&p,&r);if(r<=w/2.0)continue;double x1=sqrt(r*r-w*w/4.0);wt[cnt].left=p-x1;wt[cnt].right=p+x1;cnt++;}sort(wt,wt+cnt,cmp);double left=0,right=0;int ans=0,flag=0;if(wt[0].left<=0){int i=0,j;while(i<cnt){j=i;while(j<cnt&&left>=wt[j].left)// {if(wt[j].right>right)right=wt[j].right;j++;}if(j==i)//有区域没有被覆盖 break;ans++;left=right;i=j;//当前j为采用的那个喷水器 if(left>=l){flag=1;break;}}}if(flag)printf("%d\n",ans);elseprintf("-1\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！