题目描述

农夫约翰有 $n$ 片连续的农田，编号依次为 $1 \sim n$。
其中有 $k$ 片农田中装有洒水器。
装有洒水器的农田的编号从小到大依次为 $x_1,x_2,…,x_k$。
在某个炎热的中午，约翰觉得是时候给他的所有农田浇水了。
每个洒水器在打开以后，向两侧方向洒水，并且随着开启时间延长，有效覆盖距离也不断增长。
具体来说，我们将第 $x_i$ 片农田中的洒水器打开，经过 $1$ 秒后，第 $x_i$ 片农田被其覆盖，经过 $2$ 秒后，第 $[x_i-1,x_i+1]$ 片农田被其覆盖，经过 $j$ 秒后，第 $[x_i-(j-1),x_i+(j-1)]$ 片农田被其覆盖。
注意，每个洒水器的有效覆盖距离在每经过整数秒后，才会有所增长。
例如，经过 $2.5$ 秒后，被第 $x_i$ 片农田中的洒水器覆盖的农田仍是第 $[x_i-1,x_i+1]$ 片农田，而不是第 $[x_i-1.5,x_i+1.5]$ 片农田。
现在，约翰将所有洒水器同时打开，请问经过多少秒后，所有农田均被灌溉。

思路

灌溉的时间可看作洒水器到农田的距离。

维护一个长度为 $n$ 的数组 $a[n]$，动态存储洒水器到每片农田（ $1$ 到 $n$ ）的距离。
依次考量每个洒水器（遍历），如果当前洒水器到某一片农田的距离 比 之前存储的洒水器到这片农田的距离短，更新这个距离，即更新 $a[i]$。

要求所有农田均被灌溉的时间，所以最后答案为 $a[n]$ 中每个元素的最大值。

代码

#include <iostream>

using namespace std;

const int N = 210;

int a[N];

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for (int i = 1;i <= n;i ++ ) a[i] = 200; //因为要求每个 a[i] 的最小值，所以初始化为最大值

        while (k -- ) //遍历每个洒水器
        {
            int x; //洒水器坐标
            scanf("%d",&x);
            for (int i = 1;i <= n;i ++ ) //考虑当前的洒水器到每片农田的距离
                a[i] = min(a[i],abs(x - i) + 1); //有很多洒水器，要取它们的最小值
        }
        int res = 1;
        for (int i = 1;i <= n;i ++ )
            res = max(res,a[i]);
        printf("%d\n",res); 
    }
    return 0;
}