解题思路:
注意事项:整体思路是按照喷头的起始位置从小到大进行排序,然后依次放置喷头,直到覆盖整个地块或者没有剩余的喷头可以放置。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{
double start,end;
}a[100000];
bool cmp(node x,node y){ return x.start<y.start;}
int main()
{
int T,n,L,W; cin>>T;
while(T--)
{
cin>>n>>L>>W;
for(int i=1;i<=n;i++)
{
int p,r; cin>>p>>r;
a[i].start=0;
a[i].end=0;//记入为0,就是不满足
if(r>=W/2.0)//只有宽度足够的才有用,并被算进
{
a[i].start=p-sqrt(r*r-W*W/4.0);
a[i].end=p+sqrt(r*r-W*W/4.0);
}
}
sort(a+1,a+1+n,cmp);
int cnt=0;
double t=0;
bool flag=1;
while(t<L)
{
cnt++;
double p=t;//将变量p赋值为t,表示上一个放置点的位置
for(int i=1;a[i].start<=p&&i<=n;i++)
{
if(a[i].end>t) //现在的喷头的end大于上一个喷头的end
t=a[i].end;
}
if(p==t&&t<L)//p==t表示上一个喷头与这一个喷头一样,即没有喷头了
{
flag=0;
cout<<-1<<endl;
break;
}
}
if(flag==1) cout<<cnt<<endl;
}
return 0;
}
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:716 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:688 |
C二级辅导-等差数列 (C语言代码)浏览:591 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1087 |
C语言训练-斐波纳契数列 (C语言代码)浏览:1174 |
数组输出 (C语言代码)--此题的题目描述有问题浏览:1817 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:672 |
C语言程序设计教程(第三版)课后习题9.1 (C语言代码)浏览:681 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:567 |
核桃的数量 (C语言代码)浏览:671 |