2689 - 映雪湖畔
山东建筑大学的映雪湖畔很美。湖中央有很多FlowFish，你想去湖中央捕捉它们，可是你现在离湖中央的距离是L，不过幸亏从湖中央到你的位置有n块石头排成一条直线，现在已知每块石头距离湖中央的距离，不过你觉得有的相邻的石头之间的距离太近，你想移除m块石头，使得相邻两块石头之间的最短距离最大，为了能够捕捉FlowFish，求此距离。
Input
第一行输入一个T，代表有T组测试数据。接下来第二行包含三个整数，分别是题目中描述的L(1 ≤ L ≤ 1000)，n(0<n<100)，m(0<m<n)。接下来n行分别代表第i块石头距离湖中央的距离(0<d<L)。
Output
移除m块石头之后，相邻两块石头之间的最大的最短距离。
Examples
Input
1 25 5 2 2 14 11 21 17
Output
4
Solution C++
//524K 188MS #include<stdio.h> #include<algorithm> #define inf 0x3f3f3f3f using namespace std; int d[5007]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n,m,len; int t; scanf("%d",&t); while(t--) { scanf("%d%d%d",&len,&n,&m); d[0]=0;//起点 for(int i=1; i<=n; i++) scanf("%d",&d[i]); d[n+1]=len;//终点 n+=2; sort(d,d+n); int l=inf,r=d[n-1],mid; for(int i=1; i<n; i++)//求两块石头之间最短距离 l=min(l,d[i]-d[i-1]); while(l<=r) { mid=(l+r)/2; long long s=0,e=1,count=0; while(e<n)//枚举所有石头 { if(d[e]-d[s]>=mid)//如果这两块石头的距离大于mid，则不需要移除，更新相邻的石头 { s=e; e++; } else//如果这两块石头的距离小于mid，那么需要移除一块石头，count++，然后右面的石头往后移 { e++; count++; } } if(count>m)r=mid-1;//如果需要移除的石头的数量大于要求的数量，取下限 else l=mid+1;//否则取上限 } printf("%d\n",r); } return 0; }