【Loj #10002. 「一本通 1.1 例 3」喷水装置】题解

题目链接

题目

长 LLL 米，宽 WWW 米的草坪里装有 nnn 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W2frac{W}{2}?2??W?? 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。

请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？

思路

首先直径不足 \(w\) 直接排除。

然后我们希望每个在覆盖到左边的情况下越右越好。

所以我们按左端点排序后贪心取右端点即可。

Code

// Problem: #10002. 「一本通 1.1 例 3」喷水装置
// Contest: LibreOJ
// URL: https://loj.ac/p/10002
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
//#define N
struct node
{
	double l, r; 
}a[15010]; 
int n, m, i, j, t; 
double w, l, x, k; 
double nwmxrght, mnlft; 
int ans; 

bool cmp(node x, node y)
{
	return x.lmnlft) 
		{
			printf("-1\n"); 
			return ; 
		}
		for(; a[i].l