专栏文章

题解：UVA10382 Watering Grass

ssea_bird
UVA10382题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipnywwd
此快照首次捕获于
2025/12/03 15:06
3 个月前
此快照最后确认于
2025/12/03 15:06
3 个月前
查看原文
题目传送门。
练习贪心算法时做到这道经典题，不过有些题解仅仅是提到是能简化到区间覆盖问题，但没讲最关键的贪心思路，因此我来写一篇题解分享一下详细做法。

题目分析

题目大意

我试着上传了翻译，在这里也简述一下题目大意。
长 LL 米，宽 WW 米的草坪里装有 nn 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W2\frac{W}{2} 米）。我们已经知道每个喷头的位置（离草坪中心线最左端的距离），以及它能覆盖到的浇灌范围。
求这些喷头能否完整浇灌整块草坪，如果能，那么完成浇灌最少需要打开多少个喷头？

预处理

乍一看题目的圆形范围很难，其实可以对题目简化一下，由于圆形的弧无法完整盖住草坪，因此盖住草坪的最多只能是圆的内切矩形，再由于能够盖住那片区域的内切矩形的宽（这里记为 aa）必须要不小于整块草坪的宽（a≥Wa \ge W）才能对那片区域的覆盖产生贡献，也就是说对于 a<Wa < W 的内切矩形可以忽略，既然是圆的内切矩形，也就是说其宽一定小于圆的半径，也就是能产生贡献的圆的半径 rr 一定满足 r>Wr>W。
那么如何求出内切矩形的宽呢？根据垂径定理——垂直于弦的直径平分这条弦，且平分弦所对的两条弧，以及勾股定理可以得到，满足条件的内切矩形的宽为 WW（正好覆盖），长 bb 为 b=r2−(W2)2b=\sqrt{r^2-(\frac{W}{2})^2}，既然剩下的这些满足条件的矩形宽都为 WW，那么就只用考虑它们的长了，题目就被简化为考虑一个线段的覆盖问题了。

贪心

由于是求的最少线段数，那么为了满足这一条件，必须让每个线段能够覆盖尽可能多的未覆盖的长度（前提是已有的线段能完全覆盖整一个长的线段）。
而为了更加方便的处理，首先得将符合条件的这些线段排序，对于每个线段，开始位置靠前的排前面，当遇到开始的位置一样时结束位置靠后的排后面（每个线段的信息用结构体存储，方便处理）。
为什么开始位置相同的还要看结束位置呢？
因为假如有线段 xx 和线段 yy 它们开始位置相同，那么如果 xx 结束的位置更靠后或者说其结束位置的值更大，xx 的线段长度也就更长，符合让每个线段能够覆盖尽可能多的未覆盖的长度的思路。
接下来便是找到最优的方案了，用一个变量 rr 记录当前覆盖所能到达的最右端位置，遍历所有起点不超过 rr 的线段，如果有能够扩展覆盖范围的线段（即右端点的位置大于当前覆盖中最右端的位置），如果能满足扩展的话，就更新最右端的位置。
那么什么时候无法完全覆盖呢？对于每次更新最右端的位置的操作，如果有一次执行完更新后，其最右端的位置的值未发生变化，且并非完全覆盖完整条线段，那么说明这轮操作无法继续连续的覆盖，既然如此，由于线段都经过排序，那么新一轮的更新依旧无法补上缺漏的部分，那么就应该 cout<<-1<<'\n'。
好绕口啊 QAQ。

Code

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,w,l;
struct water{
	double begin,end;
}a[100005];

bool cmp(water x,water y){//自定义排序
	//开头靠前的排前面
	//开头一样时
	//结尾靠后的排前面
	if(x.begin!=y.begin){
		return x.begin<y.begin;
	}
	return x.end>y.end;
}
void solve(ll n,double l,double w){
    deque<ll>st;//双端队列 两端都可进出 
	ll cnt=0,ans=0;
	for(int i=1;i<=n;i++){
		double ad,r;
		cin>>ad>>r;
		if(r>(w/2)){//只处理能完全覆盖的 
            double s=sqrt((r*r)-((w/2)*(w/2)));//根据垂径定理&勾股定理得 
			a[++cnt].begin=ad-s;//矩形开始的位置 
			a[cnt].end=ad+s;
            if(a[cnt].begin<0) a[cnt].begin=0;
            if(a[cnt].end>l) a[cnt].end=l;
			//简化为线段的覆盖 
		}
	}
	sort(a+1,a+cnt+1,cmp);//按照线段的头位置 排序

	//以上为预处理
	//以下为解决区间覆盖

    double r=0;//当前已覆盖到的最右端位置
	while(r<l){
        double max_right=r; //记录在当前覆盖范围内能扩展到的最大右端点
        //遍历所有起点不超过r的线段
        for(int i=1;i<=cnt;i++){
            if(a[i].begin<=r&&a[i].end>max_right){
                max_right=a[i].end;
            }
        }
        // 检查是否找到了可以扩展覆盖范围的线段
        if (max_right==r){
            //如果没有线段能扩展覆盖范围，说明无法完全覆盖
            cout<<-1<<'\n';
            return;
        }
        //更新当前已覆盖的位置
        r=max_right;
        ans++; //使用的线段+1
    }
    cout<<ans<<'\n';
}
int main(){
	while(cin>>n>>l>>w) solve(n,l,w);
	return 0;
}
完结撒花，欢迎补充。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...