首页 > 代码库 > codeforces 51C（Three Base Stations）

codeforces 51C（Three Base Stations）

2024-07-16 04:30:06   220人阅读

【题意描述】

在高速公路的两旁有很多房子，每个房子有自己的坐标，现在给定三个基站，每个基站都有相应的覆盖半径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 }

 


联系
我们