poj 3258 最大化最小值

本文主要是介绍poj 3258 最大化最小值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//必须特判一下特殊情况，只有起始点和终点。。。。。。

#include<stdio.h>
int L,M,N,a[500050];
int judge(int x)//判断距离为x时，此时可不可行
{
     int i=0;
     int stand=0,ans=0;
     while(i<N)
     {
         while(i<N&&a[i]-stand<x)
               i++;
         if(i==N)
               return 0;
         ans++;
               stand=a[i];
         if(ans>=N-M)
         {
             if(L-stand>=x)
                return 1;
             else
               return 0;
         }
  
      }
     return 0;
 
}

void qsort(int l,int r)//快速排序
{
    int i,j,x;
    if(l<r)
    {
        i=l;
        j=r;
        x=a[i];
        while(i<j)
        {
             while(i<j&&a[j]>=x)
                 j--;
             if(i<j)
                a[i++]=a[j];
             while(i<j&&a[i]<x)
                i++;
             if(i<j)
                a[j--]=a[i];
        }
       a[i]=x;
       qsort(l,i-1);
       qsort(i+1,r);  
    }
 return;
}
int main(void)
{
        int i,l,r,m;
        scanf("%d%d%d",&L,&N,&M);
        for(i=0;i<N;i++)
           scanf("%d",&a[i]);
        if(N==0)
           printf("%d\n",L);
        else
        {
          qsort(0,N-1);
           l=0;
           r=L;
           while(l<r)
           {
                m=(l+r+1)/2;
                if(judge(m))
                   l=m;
                else
                   r=m-1;
           }
           printf("%d\n",l);
        }
}

这篇关于poj 3258 最大化最小值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---