1000ms

Difficulty: 6

所属公司 : 阿里

时间 :2025年9月11日-阿里云算法岗

算法与标签>二分算法

会员或题库专享

请先，开通会员或购买题库阿里系机考题库，可解锁完整内容。

购买阿里系机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（阿里系机考题库），可解锁完整内容。

购买题库开通会员

解题思路

模型重述

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

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

题目内容

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

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

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