游客 注册 | 登录
中文 | En

2689 - 映雪湖畔

通过次数

0

提交次数

0

时间限制 : 2 秒 内存限制 : 2048 MB

山东建筑大学的映雪湖畔很美。湖中央有很多FlowFish，你想去湖中央捕捉它们，可是你现在离湖中央的距离是L，不过幸亏从湖中央到你的位置有n块石头排成一条直线，现在已知每块石头距离湖中央的距离，不过你觉得有的相邻的石头之间的距离太近，你想移除m块石头，使得相邻两块石头之间的最短距离最大，为了能够捕捉FlowFish，求此距离。

题目输入

第一行输入一个T，代表有T组测试数据。接下来第二行包含三个整数，分别是题目中描述的L(1 ≤ L ≤ 1000)，n(0<n<100)，m(0<m<n)。接下来n行分别代表第i块石头距离湖中央的距离(0<d<L)。

题目输出

移除m块石头之后，相邻两块石头之间的最大的最短距离。

输入/输出样例

输入格式

1
25 5 2
2
14
11
21
17

输出格式

4

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;
}
请先登陆