ICPC Asia HongKong 2017-E题（二分）-蒲公英云

ICPC Asia HongKong 2017-E题（二分）

野性酷女 2023-08-17 16:26 184阅读 0赞

题目：https://www.jisuanke.com/contest/3820/255960

思路：二分找最短距离

在一条直线上有n个点，找m个点尽量使其最短距离都很大 a[0]到a[n-1]从小到大排列

我们有一个原则，那就是第一个点一定是在a[0] 我们可以想一想如果不在a[0] 假设在a[t] 而要距离的点a[x] 要使其两点距离远一点我们肯定选a[0]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
int n,m;
int a[maxn];
int solve(int mid)
{
    int t=0,i=1;  //根据直线多个点距离最优原则   第一个机器一定放在第一个位置
    int sum=1;
    while(i<n)
    {
        if(a[i]-a[t]>=mid)//说明两点距离大于等于mid(最小距离)
        {
            sum++;
            t=i;
        }
        i++;
    }
    if(sum>=m)//说明存在大于等于m个点的个数可以使距离不小于最小距离
        return 1;
    else
        return 0;
}
int main()
{
    while(~scanf("%d %d",&n,&m)){
    if(n==0&&m==0)
    break;
    int r=0,l=0,mid;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    //二分求答案
    sort(a,a+n);
    r=a[n-1];
    while(l<=r)
    {
        mid=(l+r)/2;
        if(solve(mid)==1)//说明可以达到最小距离为mid
            l=mid+1;
        else
            r=mid-1;
    }
    printf("%d\n",l-1);
    }
}