nyoj--12--喷水装置（二）（区间覆盖问题+贪心）

喷水装置（二）

时间限制：3000 ms | 内存限制：65535 KB

难度：4

描述

有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。

输入

第一行输入一个正整数N表示共有n次测试数据。

每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。

随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。

输出

每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。

如果不存在一种能够把整个草坪湿润的方案，请输出0。

样例输入

样例输出

1

2

来源

《算法艺术与信息学竞赛》

上传者

张云聪

一个挺好的区间问题，总的思想就是sum来记录现在最远覆盖的距离，每一次遍历找到新的效率最大的装置，如果找不到就跳出循环

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

using namespace std;

struct node

{

	double l,r;

}edge[1001];

bool cmp(node s1,node s2)

{

	return s1.l<s2.l;

}

int main()

{

	int t;

	scanf("%d",&t);

	while(t--)

	{

		int n,w,len;

		int x,r;

		scanf("%d%d%d",&n,&len,&w);

		double w2=1.0*w/2.0;

		for(int i=0;i<n;i++)

		{

			scanf("%d%d",&x,&r);

			double x2=sqrt(r*r-w2*w2);

			if(x2>0)

			{

				edge[i].l=x-x2;

				edge[i].r=x+x2;

			}

		}

		sort(edge,edge+n,cmp);

		double MAX=0;

		double sum=0;//sum来记录现在已经覆盖的长度，也算是终点的坐标

		int count=0,flog=1;

		while(sum<len)

		{

			MAX=0;//用MAX来记录最长的更新的距离

			for(int i=0;i<n&&edge[i].l<=sum;i++)

			{//每一次遍历找最长的更新距离，并且起点至少在sum以内

				if(edge[i].r-sum>MAX)

				{

					MAX=edge[i].r-sum;

				}

			}

			if(MAX==0)

			//如果一次遍历没有更新的距离，说明有一段无法覆盖或者装置不够用

			{

				flog=0;

				break;

			}

			else

			{

				count++;//找到新的装置，计数变量加一并且sum更新

				sum+=MAX;

			}

		}

		if(flog)

		printf("%d\n",count);

		else

		printf("0\n");

	}

	return 0;

}

巴特西

nyoj--12--喷水装置（二）（区间覆盖问题+贪心）

喷水装置（二）

最新文章

热门文章