返回信息流/*描述
有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。
**输入
第一行输入一个正整数N表示共有n次测试数据。
每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。
随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。
**输出
每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。
如果不存在一种能够把整个草坪湿润的方案，请输出0。
**样例输入
2
2 8 6
1 1
4 5
2 10 6
4 5
6 5
**样例输出
1
2*/
#include<stdio.h>
#include<math.h>
int N;
int count=0;
float findMax(float *arr)
{
float max=arr[0];
int i;
for(i=1;arr[i]<=10000;i++)
{
if(arr[i]>max)
max=arr[i];
}
return max;
}
int main()
{
int n,w,h,i,n_temp,j;float max;
int xi[10000],ri[10000];
float start[10000],end[10000],temp,end_temp[10000];
scanf("%d",&N);
while(N--)
{
scanf("%d %d %d",&n,&w,&h);
i=0;
n_temp=n;
while(n_temp--)
{
scanf("%d %d",&xi[i],&ri[i]);
if(2*ri[i]>h)//************喷水装置范围入数组
{
if(xi[i]+sqrt(ri[i]*ri[i]-h*h/4)>w||xi[i]<sqrt(ri[i]*ri[i]-h*h/4))
{
if(xi[i]+sqrt(ri[i]*ri[i]-h*h/4)>w)
{
end[i]=w;
if(xi[i]<sqrt(ri[i]*ri[i]-h*h/4))
start[i]=0;
else start[i]=xi[i]-sqrt(ri[i]*ri[i]-h*h/4);
}
if(xi[i]<sqrt(ri[i]*ri[i]-h*h/4))
{
start[i]=0;
if(xi[i]+sqrt(ri[i]*ri[i]-h*h/4)>w)
end[i]=w;
else end[i]=xi[i]+sqrt(ri[i]*ri[i]-h*h/4);
}
}
else
{
end[i]=xi[i]+sqrt(ri[i]*ri[i]-h*h/4);
start[i]=xi[i]-sqrt(ri[i]*ri[i]-h*h/4);
}
i++;
}
}
for (j = 0, temp = 0; j <= n&&temp != w; j++)//***********贪心选择
{
for (i = 0; i <= n; i++)
if (start[i] <= temp&&end[i] > temp)
end_temp[i] = end[i];
temp = findMax(end_temp);
count++;
for (i = 0; i<n + 1; i++)
end_temp[i] = 0;
}
if(temp==w)//************输出结果
printf("%d\n",count);
else printf("0\n");
temp=0;count=0;//***********初始化变量
for(i=0;i<n+1;i++)
{
end_temp[i]=0;
end[i]=0;
start[i]=0;
}
}
return 0;
}
这是一条镜像帖。来源：北邮人论坛 / student-query / #6570同步于 2017/12/27
该镜像源已超过 30 天没有更新，可能在源站已被删除。
StudentQuery机器人发帖
求帮忙看下oj题(南阳oj喷水2，不知道错哪了
whchen5
2017/12/27镜像同步0 回复
订阅后，新回复会通过你的通知中心匿名送达。
0 条回复
暂无回复 · 你可以订阅本帖等待新回复。