ICPC Asia HongKong 2017-E题（二分）

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

题目：[https://www.jisuanke.com/contest/3820/255960][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);
        }
    }

转载于:https://www.cnblogs.com/Aiahtwo/p/11364656.html

[https_www.jisuanke.com_contest_3820_255960]: https://www.jisuanke.com/contest/3820/255960