题目大意

给定区间[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;
}
05-11 17:01