首页 > 代码库 > codeforces 51C(Three Base Stations)
codeforces 51C(Three Base Stations)
【题意描述】
在高速公路的两旁有很多房子,每个房子有自己的坐标,现在给定三个基站,每个基站都有相应的覆盖半径d,现在要使基站覆盖所有的房子,问基站应该如何建,并且最小的覆盖半径是多少?
【解题思路】
我们可以对基站的覆盖半径进行二分,二分的左区间端点l是0,右区间端点r是c[n]-c[1]即所有房子所占据的范围。这样就可以把基站半径算出来了,求基站的坐标时有点小技巧,看看下面的代码就知道了。
【AC代码】
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 #define max 2*100000+5 6 int c[max]; 7 int ans[3]; 8 int n; 9 int fnext(int x)//求每一个基站所覆盖范围之外的下一个坐标10 {11 int l=1,r=n+1;12 int mid=(l+r)/2;13 while(l<r)14 {15 if(c[mid]<=x) l=mid+1;16 else r=mid;17 mid=(l+r)/2;18 }19 return mid;20 }21 int ok(int x)22 {23 int z=1;24 for(int i=0;i<3;i++)25 {26 z=fnext(c[z]+x);//这里是求某一个基站所覆盖房屋的右端的下一座房子27 ans[i]=z;//存储z方便求出基站坐标28 if(z>=n+1) return 1;29 }30 return 0;31 }32 int main()33 {34 while(cin>>n)35 {36 for(int i=1;i<n+1;i++)37 {38 cin>>c[i]; 39 }40 sort(c+1,c+1+n);41 int r=c[n]-c[1];42 int l=0,mid=(l+r)/2;43 while(l<r)44 {45 if(ok(mid)) r=mid;46 else47 l=mid+1;48 mid=(r+l)/2;49 } 50 ok(l);51 double radious=l*1.0/2.0;52 double radar1=(c[ans[0]-1]+c[1])*1.0/2.0;53 double radar2=(c[ans[1]-1]+c[ans[0]])*1.0/2.0;54 double radar3=(c[ans[2]-1]+c[ans[1]])*1.0/2.0;55 printf("%.6f\n",radious);56 printf("%.6f ",radar1);57 printf("%.6f ",radar2);58 printf("%.6f\n",radar3); 59 }60 return 0;61 62 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。