nyoj--586（疯牛） && poj --2456-白红宇

nyoj--586（疯牛） && poj --2456

阅读量：4286 次

发布时间：2019-05-27

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

题意：给你n个点，在这n个点中插入m个点，使得m个点的距离尽可能的大，求尽可能大的距离值最小

#include
   
    #include
    
     #include
     
      using namespace std;int n,m,a[100005];bool Greedy(int cur)//贪心查找符合条件的距离{    int ret = a[0];    int count = 0;    for(int i = 1;i < n;i++)    {        if(a[i] - ret >= cur)        {            count ++;            ret = a[i];        }    }    if(count >= m-1) return true;//当满足大于、等于 m - 1，说明存在，返回true；    return false;}void search(int l,int r)//二分枚举这个距离{    while(l <= r)    {        int mid = (l + r) / 2;        if(!Greedy(mid)) r = mid - 1;   //if为假，说明此时这个距离太大，不符合条件        else l = mid + 1;               //if为真，说明此时这个距离满足条件，继续寻找更满足条件的距离    }    printf("%d\n",l-1);}int main(){    while(scanf("%d%d",&n,&m)!=EOF)    {        for(int i = 0;i < n;i++)            scanf("%d",&a[i]);        sort(a,a+n);        search(0,a[n-1]);    }    return 0;}