解题思路

把每次“手动染黑”看成在时间点 t 出现的一个“源点” a_t。第 t+1, t+2, … 秒的开始，这个源点会以每秒 1 格的速度向左右扩散。因此，到第 T 秒结束时，这个源点能覆盖的区间为

[a_t-(T-t),\; a_t+(T-t)]

P3649.第3题-网格染色

1000ms

Difficulty: 6

所属公司 : 阿里

算法与标签>二分算法

有一条长度为 $n$ 的一维网格(编号为 $1$ ~ $n$ )。初始时，所有网格均为白色。从第 $1$ ~ $m$ 秒，每一秒结束前会给出一个整数 $a_t$ ,表示将编号为 $a_t$ 的网格手动染成黑色。

同时，过程按秒进行、且在 $m$ 秒之后也继续进行:在每一秒开始时，所有已经为黑色的网格会同时将其左右相邻(编号相差为 $1$ )的白色网格染成黑色(若相邻位置不存在则忽略)。

请计算:最少经过多少秒结束时，所有网格都被染成黑色。

更明确的时间线(同一秒内按如下顺序执行):
- 在第 $t$ 秒开始时，所有黑色网格同时向左右各扩散 $1$ 格，将相邻白色网格染黑;
- 若 $t≦m$ ，则在第 $t$ 秒结束前，额外将编号为 $a_t$ 的网格手动染黑(若已为黑色则无额外影响)。
在 $t>m$ 时不再有手动染色，但“每秒开始时的扩散”仍持续进行，直到全体网格变黑为止。

你需要输出满足“在第t秒结束时全黑”的最小 $t$ 。

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦T≦10^4)$ 代表数据组数，每组测试数据描述如下:

第一行输入两个整数 $n,m(1≦n≦10^9;1≦m≦2×10^5)$ 表示网格长度与手动染色的次数;

第二行输入 $m$ 个整数 $a_1,a_2,...,a_m (1≦a_i≦n)$ 表示第 $t$ 秒结束前手动染黑的网格编号。

除此之外，保证单个测试文件的 $m$ 之和不超过 $2×10^5$ 。

对于每一组测试数据，新起一行，输出一个整数，表示在第 $t$ 秒结束时全体网格变黑所需的最少秒数

输入

输出

3
5

说明

初始全白。

对于样例一：

对于样例二：

输入

预期输出（选填）