#10002. 「一本通 1.1 例 3」喷水装置

时间:2024-03-24 12:25:11

[题目描述]题目题目题目

题目数据(这道题比较悬殊,直接上传可能会unkown,所以用数据过了就算了吧)

Source: UVa 10382

长 L 米,宽 W米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上(离两边各 W/2米)。我们知道每个喷头的位置(离草坪中心线左端的距离),以及它能覆盖到的浇灌范围。

请问:如果要同时浇灌整块草坪,最少需要打开多少个喷头?

#10002. 「一本通 1.1 例 3」喷水装置

[输入格式]

输入包含若干组测试数据。

第一行一个整数 T表示数据组数;

每组数据的第一行是整数 n、L 和 W;

接下来的 n 行,每行包含两个整数,给出一个喷头的位置和浇灌半径(上面的示意图是样例输入第一组数据所描述的情况)。

[输出格式]

对每组测试数据输出一个数字,表示要浇灌整块草坪所需喷头数目的最小值。如果所有喷头都打开也不能浇灌整块草坪,则输出 −1 。

[样例输入]

3
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1

[样例输出]

6
2
-1

[数据范围与提示]

对于 %100% 的数据,n≤15000

鬼畜思路:我今天想用绿色我也不知道为什么,别想多我没被绿,我可是有女朋友的,这道题刚看可能会有点晕晕的,但是其实这道题就是一道典型的贪心“区间覆盖问题”。重点在此:这道题的话,其实就是在可以达到的长度上找出极限的区间长度,来做到贪心,而且每一步都是为了找最大的区间。变成蓝色了,然后的话,可能会有一个想不到的,就是这道题要用到勾股定理,

#10002. 「一本通 1.1 例 3」喷水装置

不难看出,这个所覆盖的长度其实就是形成了一个三角形,有两条边相等,让你求长边。

#10002. 「一本通 1.1 例 3」喷水装置

#10002. 「一本通 1.1 例 3」喷水装置

我把贪心策略的实现用图来表示一下(参考了一个大佬的博客膜拜大佬

#10002. 「一本通 1.1 例 3」喷水装置 这是一个区间

贪心策略

#10002. 「一本通 1.1 例 3」喷水装置

 

#10002. 「一本通 1.1 例 3」喷水装置 

#10002. 「一本通 1.1 例 3」喷水装置

 

#10002. 「一本通 1.1 例 3」喷水装置 

这个就是贪心的全过程 ,只要把贪心的概念理解清楚就很简单了

/*
理解题意:喷水装置是一道非常好的贪心经典题,属于“区间覆盖问题”
题目简化:给定一条线段(区间)l(其端点为A, )和 k个区间(p,q) ,
请选用最少的区间覆盖这一条线段(区间)
贪心策略
将所有的区间按照左端点从小到大排序,选择覆盖点A的区间中右端点最大的一个,
并将A更新为这个区间右端点的坐标,再次选择覆盖点A的区间中右端点最大的一个,
将A更新为这个区间右端点的坐标,如此往复,直到覆盖了点B
一些小细节
刚刚我们针对贪心-区间覆盖问题 谈了很多,不过,对于本题,
还有一些小细节需要注意,如下:
读入的是喷水装置(即一个圆)的半径r, 而不是覆盖的范围,覆盖范围应该是:
a[k].x=o-sqrt(r*r-(w/2)*(w/2))
a[k].x=o+sqrt(r*r-(w/2)*(w/2))
(其实这个就是一个勾股定理) 
这里x和y是区间的左右端点,o为喷水装置的坐标,
即喷水装置喷水范围的圆心,r为其半径,w为草坪的宽度
如果喷水装置的半径小于草坪的宽度,那么这个喷水装置肯定不能用,
因为它一块区间都覆盖不了

这道题简单来讲就是一直在找一个最大值
找到了如果当前是最大的区间就把记录喷头数的ans+1
大概就是这样的一个思路  
*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()//沙雕快读,我在博客里面有关于快读的解释,不喜欢的可以换成其他的 
{
	char c=getchar();
	int x=0,f=1;
	while(c<48 || c>57)
	{
		if(c=='-') f=-1;
		c=getchar();
	}	
	while(c>=48 && c<=57)
	{
		x=x*10+c-48;
		c=getchar();
	}
	return x*f;
} 
struct node
{
	double x,y;//x-y这一区间的长度 
}a[15010];
int n,last,ans;
double st,ed,l,w; 
int cmp(node n1,node n2)
{
	return n1.x<n2.x;//头越小,整个区间就越长 
}
inline double gougu(double r)//勾股定理 
{
	return sqrt(r*r-(w/2)*(w/2));//园利用三角形的勾股定理来求出覆盖的长度 
}
int main()
{
	int t; t=read();
	while(t--)
	{
		scanf("%d%lf%lf",&n,&l,&w);
		double o,r;
		for(int i=1;i<=n;i++)
		{
			scanf("%lf%lf",&o,&r);
			if(r<(w/2)) a[i].x=a[i].y=0;
			/*
			如果浇灌的半径大于宽的一半,其实就是长度大于宽的话,
			那么这个区间就不需要记录,因为这个可以直接实现 
			*/ 
			else a[i].x=o-gougu(r),a[i].y=o+gougu(r);
			//否则利用勾股求出最小的头和最大的尾 
		}
		sort(a+1,a+n+1,cmp);//这是贪心的一步 
		st=0,ed=0,last=0,ans=0;
		//st是用来保存当前所到的区间的头 //ed是用来保存当前所到区间的尾
		//last是用来表示当前到的喷头数   //ans是用来保存已经使用的喷头 
		while(ed<l && last<=n)//当还有喷头并且没有到尽头的时候进入 
		{
			for(int i=last+1;i<=n;i++)
			{
				if(a[i].x<=st)//如果当前的区间的头小于之前的,就记录 
				{
					if(a[i].y>ed) 
					{
						ed=a[i].y;
						last=i;
					}//说明找到了最新数据的区间也就是最长的(贪心) 
				}
				else break;
			}
			if(ed==st)
			//如果这个尾等于头,说明就算打开全部喷头也做不到,就输出-1 
			{
				ans=-1;
				break;//不能return 0是因为有多组数据 
			}
			st=ed; ans++;
			/*
			否则就可以把当前的头记录成尾巴,使用一个喷头,
			说明这一个区间是成立中的最大的 
			*/ 
		}
		if(last>n) printf("-1\n");//如果最后用到的喷头数大于拥有的,输出-1 
		else printf("%d\n",ans);//否则输出用到的最少的喷头数 
	}
	return 0;
}

蒟蒻写的代码,有错的大佬尽情吐槽