UVa 10382 - Watering Grass 发表于 2014-12-05 | 分类于 AOAPC Training Guide , Chapter 1. Algorithm Design , General Problem Solving Techniques | 贪心法,区间覆盖问题。蓝书开始这几道题还真是水啊。12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include<iostream>#include<algorithm>#include<vector>#include<cmath>using namespace std;struct sp{ double o,r,l1,l2; bool operator <(const sp &a)const{ if(l1==a.l1) return l2<a.l2; else return l1<a.l1; }};int main(){ int n,l; double w; while(cin>>n>>l>>w){ w/=2; vector<sp> a; sp t; while(n--){ cin>>t.o>>t.r; if(t.r>w){ double k=sqrt(t.r*t.r-w*w); t.l1=t.o-k; t.l2=t.o+k; if(t.l1<0) t.l1=0; if(t.l2>l) t.l2=l; a.push_back(t); } } sort(a.begin(),a.end()); bool flag=false; int cnt=0,last=0; double now=0,maxn=0; while(now<l){ for(int i=last;i<a.size();i++){ if(a[i].l1<=now){ maxn=max(maxn,a[i].l2); last++; flag=true; } else break; } if(flag) flag=false; else{ cnt=-1; break; } now=maxn; cnt++; } cout<<cnt<<endl; } return 0;}本文迁移自我的 CSDN博客 ,格式可能有所偏差。