题目描述

农夫约翰有 n 片连续的农田，编号依次为 1∼n。

其中有 k 片农田中装有洒水器。

装有洒水器的农田的编号从小到大依次为 x1,x2,…,xk。

在某个炎热的中午，约翰觉得是时候给他的所有农田浇水了。

每个洒水器在打开以后，向两侧方向洒水，并且随着开启时间延长，有效覆盖距离也不断增长。

具体来说，我们将第 xi 片农田中的洒水器打开，经过 1 秒后，第 xi 片农田被其覆盖，经过 2 秒后，第 [xi−1,xi+1] 片农田被其覆盖，经过 j 秒后，第 [xi−(j−1),xi+(j−1)] 片农田被其覆盖。

注意，每个洒水器的有效覆盖距离在每经过整数秒后，才会有所增长。

例如，经过 2.5 秒后，被第 xi 片农田中的洒水器覆盖的农田仍是第 [xi−1,xi+1] 片农田，而不是第 [xi−1.5,xi+1.5] 片农田。

现在，约翰将所有洒水器同时打开，请问经过多少秒后，所有农田均被灌溉。

算法1

因为每个农田都会首先被最近的那个喷水器覆盖，所以只考虑相隔喷水器最远的那个，就是最后覆盖的
因为头和尾是特殊的，不能用中间值去算
所以先掐头去尾，最后再考虑头尾

C++ 代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[210];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k,time=0,mid=0,maxv=0; //初始化

        cin>>n>>k;
        for(int i=1;i<=k;i++) cin>>a[i];


        for(int i=1;i<=k-1;i++) //不算第一个和最后一个喷水器，只考虑中间相邻喷水器的最大相隔距离
            maxv=max(maxv,a[i+1]-a[i]-1);

        mid=maxv+1 >> 1;//中间田地的位置

        time=mid+1; //不考虑头尾的最大时间

        time=max(time,a[1]); //和第一个喷水器前面的田地覆盖时间比较
        time=max(time,n-a[k]+1); //和最后一个喷水器后面的田地覆盖时间比较

        cout<<time<<endl;
    }
    return 0;
}