GitBook

这里写图片描述 这里写图片描述

也是一道**化最*值的题 掌握技巧之后这种题还是很简单的

思路都是通过二分来查找答案 然后判断这个答案符不符合要求 这样的话便可以不断二分 来缩小答案所在区间大小

这一题判断答案是否符合的方式 如果最小值是x 那么若想让答案成立 需要去除几个石头 很显然 若想要让答案符合条件 需要去除的石头需要 cnt<=m

通过二分 便可以找到让答案符合的 最大的那个res

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[50200];
int l,n,m;
bool judge(int x) {
	if(x==0)
		return false;
	int cnt=0,last=0;
	for(int i=1; i<n; i++) {
		int t=a[i]-a[last];
		if(t<x)
			cnt++;
		else
			last=i;
	}
	if(cnt>m)
		return false;
	else
		return true;
}
int main() {
	while(scanf("%d %d %d",&l,&n,&m)!=EOF) {
		a[0]=0;
		for(int i=1; i<=n; i++)
			scanf("%d",&a[i]);
		a[(++n)++]=l;
		sort(a,a+n);
		int la=0,lb=l;
		int mid,res;
		while(lb>=la) {
			mid=(la+lb)/2;
			if(judge(mid)) {
				res=mid;
				la=mid+1;
			} else
				lb=mid-1;
		}
		printf("%d\n",res);
	}
	return 0;
}

题目地址:【POJ】[3258]River Hopscotch