【題意】

牛要到河對岸，在與河岸垂直的一條線上，河中有N塊石頭，給定河岸寬度L，以及每一塊石頭離牛所在河岸的距離，

現(xiàn)在去掉M塊石頭，要求去掉M塊石頭后，剩下的石頭之間以及石頭與河岸的最小距離的最大值。

Sample Input

25 5 2
2
14
11
21
17

Sample Output

4
分析：其實這個和Agressive Cows這道題差不多，只要把起點與終點加入到數(shù)組中，然后留下找（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[51000];
bool cmp (int x,int y)
{return x<y;
}
bool C(int d)
{int last=0;for(int i=1 ; i<(n-m+2) ; i++){int crt=last+1;while(crt<n+2&&a[crt]-a[last]<d)crt++;if(crt==n+2)return false;last = crt;}return true;}
int main()
{scanf("%d%d%d",&l,&n,&m);for(int i = 1 ; i <= n ; i++)scanf("%d",&a[i]);a[n+1]=l;sort(a,a+n+1,cmp);int en=INF;int st=0;while(en-st>1){int mid=(st+en)/2;if(C(mid))st=mid;elseen=mid;}printf("%d\n",(st+en)/2);return 0;
}

View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/shuaihui520/p/8929049.html

總結(jié)

以上是生活随笔為你收集整理的POJ 3258：River Hopscotch (最大化最小值）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。