POJ3258跳房子

思路分析:要求母牛跳跃最短距离的最大值.暴力的判断肯定不行,复杂度太高.因为每个石头间的距离已知,我们可以通过距离来判断石头是否可以放的下.所以二分法寻找最小距离,然后判断即可.

#include
#include
using namespace std;
const int maxsize = 50000 +10;
int dis[maxsize],l,n,m,ans,mid;

int judge(int x) { // 最小距离为x
	int last = 0;
	int num = n - m;//减掉m个石头 
	int cur;//放置num个石头，循环num次
	for(int i = 0; i < num; i++) { //对于这些石头，要使任意间距不小于x
		cur = last + 1;//当前石头的编号 
		while(cur<=n&&(dis[cur]-dis[last]=x才能放石头 
			cur++;//不满足,则继续判断下一个. 
		}
		if(cur>n) {//如果石头总数大于n了,则说明距离过大了,能放置的石头太少. 
			return 0;
		}
		last = cur;//更新上一块石头的编号.继续判断下一个石头是否可以放置.. 
	}
	return 1;
}

int main() {
	cin>>l>>n>>m;
	for(int i = 1; i <= n; i++) {
		cin>>dis[i];
	}
	if(n==m) {
		cout<