POJ 3258:River Hopscotch (最大化最小值)

时间:2023-03-09 19:30:09
POJ 3258:River Hopscotch (最大化最小值)

【题意】

牛要到河对岸,在与河岸垂直的一条线上,河中有N块石头,给定河岸宽度L,以及每一块石头离牛所在河岸的距离,

现在去掉M块石头,要求去掉M块石头后,剩下的石头之间以及石头与河岸的最小距离的最大值。

Sample Input

25 5 2
2
14
11
21
17

Sample Output

4
分析:其实这个和Agressive Cows这道题差不多,只要把起点与终点加入到数组中,然后留下找(N-M+2)个位置之间的最大值,类比与Agressive cows的M;
具体题解可看Agressive cows AC代码:
#include<stdio.h>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int n,m,l;
int a[];
bool cmp (int x,int y)
{
return x<y;
}
bool C(int d)
{
int last=;
for(int i= ; i<(n-m+) ; i++)
{
int crt=last+;
while(crt<n+&&a[crt]-a[last]<d)
crt++;
if(crt==n+)
return false;
last = crt;
}
return true; }
int main()
{
scanf("%d%d%d",&l,&n,&m);
for(int i = ; i <= n ; i++)
scanf("%d",&a[i]);
a[n+]=l;
sort(a,a+n+,cmp);
int en=INF;
int st=; while(en-st>)
{
int mid=(st+en)/;
if(C(mid))
st=mid;
else
en=mid;
}
printf("%d\n",(st+en)/);
return ;
}