本文共 912 字，大约阅读时间需要 3 分钟。

（uva上的数据有问题，计蒜客可以交）

题目大意：

       要在S个用户接入点上建L个基站（基站个数L<用户接入点个数，且基站一定是建在接入点上），建基站的原则是相邻基站之间的距离尽可能大，问基站之间的距离最小是多少

题解：

      二分答案

      将第一个点固定在最左边的基站，然后二分基站之间的距离，如果当前接入点到上一个基站的距离大于mid，就选这个接入点建一个基站，否则往下走。如果在中途基站就选完了，说明基站之间的距离小了，l=mid+1，否则是大了r=mid-1

#include
   
    #include
    
     #define ll unsigned long longusing namespace std;int a[100010];int S,L;bool check(int mid){    int l=1;    int num=L-1;    for(int i=2;i<=S;++i)    {        if(a[i]-a[l]>=mid)        {            l=i;            --num;            if(num==0)return 1;        }    }    return 0;}int main(){    while(~scanf("%d%d",&S,&L))    {        if(S==0 && L==0)return 0;        for(int i=1;i<=S;++i)            scanf("%d",&a[i]);        sort(a+1,a+1+S);        int l=0,r=1000010;        while(l<=r)        {            int mid=(l+r)>>1;            if(check(mid))                l=mid+1;            else r=mid-1;        }        printf("%d\n",r);    }    return 0;}
    
   

转载地址：http://qufgf.baihongyu.com/