题目链接:https://cn.vjudge.net/contest/311860#problem/C
Sample Input
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 1Sample Output
6 2 -1解析:刚开始输入三个数，8 20 2。8个圆，矩形的长宽分别是20和2。 接下来8组数据: 每一组表示圆心离最左端的距离，和圆的半径。 问：把矩形完全覆盖，最少需要几个圆？ 分析：需要解决：1.对数据如何处理，转化为熟悉的一个序列的问题。2.如何贪心？ 图1 图二
所需的圆必须满足：1.直径大于矩形的宽度。2.圆覆盖的有效长度不是直径。（如图2，蓝色的没被覆盖），图1，红色部分是有效长度。覆盖的有效范围，转化为线段的长度。
贪心的问题：每一个线段的左端点，从小到大排序。贪心结束后，最最左边的端点必须保证小于或等于矩形的最左端。最最右边的端点必须保证大于或等于矩形的最右端。找到第一个左端点小于矩形左端点的线段，for循环，保证最右边尽可能大。for循环结束后，只找到一个。再进行for循环，找下一个。。。。。直至满足，找到一个线段的右端点大于或等于矩形的长度。
代码：
#include<cstdio> #include<cstring> #include<cmath> #include<stdlib.h> #include<algorithm> using namespace std; int n,l,w; int book[10005]; int k;//k为"有效圆"的个数 struct node{ double len;//圆心到左端点的长度 double limit1;//左范围 double limit2;//右范围 } s[10005]; int cmp(node x,node y){ return x.limit1<y.limit1;//左范围从小到大排序 } int main(){ double len1,r1; while(~scanf("%d%d%d",&n,&l,&w)){ k=0;//n个圆，草坪的长宽分别是l和w for(int i=0; i<n; i++)//符合情况的存到结构体中 { scanf("%lf %lf",&len1,&r1); if(2*r1>w){ s[k].len=len1; s[k].limit1=len1-sqrt(r1*r1-(w*w)/4.0); s[k++].limit2=len1+sqrt(r1*r1-(w*w)/4.0); } } sort(s,s+k,cmp); if(s[0].limit1>0){ printf("-1\n"); continue; } int sum=0,flag,h; double head=0,tail=0; memset(book,0,sizeof(book)); while(1){ flag=0; for(int i=0; i<k; i++){ if(s[i].limit1<=head&&s[i].limit2>=tail&&book[i]==0){ flag=1; tail=s[i].limit2;//保证最右边尽可能的大 if(tail>=l) flag=2; h=i; } } if(flag==1||flag==2){ book[h]=1; sum++; head=tail; } else break; if(flag==2) break; } if(tail<l) flag=0; if(flag==0) printf("-1\n"); else printf("%d\n",sum); } return 0; }后记：也是降维处理的贪心：https://blog.csdn.net/lylzsx20172018/article/details/96123305
