poj_3258 二分法

题目大意

给定区间[0,L]，在区间内给定N个数，加上区间的端点总共N+2个值。这N+2个数相邻的两个数之间有一个差值delta[i]，现在可以从除去端点之外的这N个数中删除M个，使得剩余的N+2-M个数相邻数的最小差值最大。求这N+2-M个数相邻数的最小差值的最大值。

题目分析

典型的最大化最小值问题，最大化/最小化 最大值/最小值/平均值的问题，通常可以考虑使用二分法。如果对于一个数x，判断x是否满足题目要求的时间复杂度不高，那么可以尝试枚举x（当然如果x满足要求，那么所有比x大（或者所有比x小）的数都满足要求，则可以使用二分法枚举）。 
    题目中位置0和位置L处的数字不能删除，假设从N个数中删除M个，可以使得相邻数字的最小差值为x。那么就从位置0开始考虑，寻找下一个和当前数字差值小于x的数a，将a删除... 直到删除数字为M个或者到达N+1的位置停止。若还没删除M个就已经到达了N+1的位置，则说明必定可以使得相邻数字的最小差值大于等于x；若已经删除了M个，则考虑剩余的那些数字中的相邻差值是否小于x，若小于，则说明不满足要求。 
    此题关键的一点是位置0处的数字不能删除，这样就可以从位置0开始考虑，用类似贪心的方法，通过最小距离大于等于x来覆盖到N+1。

实现(c++)

#include<stdio.h>

#include<cmath>

#include<algorithm>

using namespace std;

#define MAX_N 50005

int gDist[MAX_N];

//判断能否从n个数字中删除m个，使得相邻最小距离大于等于 min_dist

bool CanSet(int n, int m, int min_dist){

	int last_i = 0;

	int i = 1;

	int c = 0;

	while (i <= n && c < m){

		if (gDist[i] - gDist[last_i] < min_dist){

			c++;

		}else

			last_i = i;

		i++;

	}

	if (c == m){

		if (gDist[i] - gDist[last_i] < min_dist) //注意考虑 i和 last_i

			return false;

		for (; i <= n; i++)

			if (gDist[i + 1] - gDist[i] < min_dist)

				return false;

	}

	return true;

}

int main(){

	int l, n, m;

	while (scanf("%d %d %d", &l, &n, &m) != EOF){

		gDist[0] = 0;

		gDist[n + 1] = l;

		for (int i = 1; i <= n; i++){

			scanf("%d", gDist + i);

		}

		sort(gDist, gDist + n + 2);

		int beg = 1, end = l + 1;	//二分法，左闭右开！！ 故用 l+1

		while (beg < end){

			int mid = (beg + end) / 2;

			if (CanSet(n, m, mid))

				beg = mid + 1;

			else

				end = mid;

		}

		printf("%d\n", beg - 1);

	}

	return 0;

}