解题思路

模型重述

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

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

（当 $T < t$ 时该源点尚未出现，不产生覆盖；区间记得与 $[1,n]$ 取交）。

于是问题等价为：求最小的 $T$，使得

$$\bigcup_{t=1}^{\min(m,T)} [\max(1,a_t-(T-t)),\; \min(n,a_t+(T-t))] \supseteq [1,n].$$

这显然可以用“判定 + 二分”解决。

判定函数（是否在第 T 秒结束时全黑）

构造所有在 $t \le T$ 的源点区间，按左端点从小到大排序，线性扫描合并并检查能否无缝覆盖 [1,n] 即可。

小优化（预排序 O(1) 次、判定 O(m)）： 注意左端点

$$L_t=a_t-(T-t)=(a_t+t)-T$$

对同一组数据来说，$(a_t+t)$ 是与 $T$ 无关的常数。因此我们可以预先按键 key = a_t + t 将所有源点排序一次；之后每次判定只需按这个固定顺序遍历（过滤掉 t > T 的源点），计算对应区间并线性扫一遍即可，无需每次再排序。

二分边界

• 下界 lo = 0（显然不可能，但便于统一写法）。
• 上界 hi = n + m：最多等到所有手动染色都发生（m 秒），再向最远端扩散不超过 n 秒，必定覆盖。

整体就成了：在 [0, n+m] 上二分最小的可行 T。

复杂度分析

• 预排序一次：$O(m \log m)$。
• 每次判定：线性 $O(m)$。
• 二分次数：$\lceil \log_2(n+m+1)\rceil \le 40$（因 $n \le 10^9$）。
• 总体：$O(m \log m + m \log(n+m))$。题目保证单测文件内 $\sum m \le 2\times10^5$，完全可过。

代码实现

Python

import sys

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    T = next(it)
    out_lines = []

    for _ in range(T):
        n = next(it)
        m = next(it)
        a = [next(it) for _ in range(m)]

        # 预处理：保存 (keyL = a_t + t, keyR = a_t - t, t, a_t)
        # t 采用 1-based
        pts = []
        for i, x in enumerate(a, start=1):
            pts.append((x + i, x - i, i, x))
        pts.sort(key=lambda v: v[0])  # 按 a_t + t 排序（固定顺序）

        def ok(TT: int) -> bool:
            if TT <= 0:
                return False
            cur = 1  # 当前已覆盖到的下一个位置
            # 遍历预排好序的源点
            for keyL, keyR, t, x in pts:
                if t > TT:
                    continue  # 该源点尚未出现
                # 计算该源点在第 TT 秒结束时的覆盖区间
                # L = (a_t + t) - TT, R = (a_t - t) + TT
                L = keyL - TT
                R = keyR + TT
                if R < 1 or L > n:
                    continue  # 与 [1, n] 无交
                if L < 1:
                    L = 1
                if R > n:
                    R = n
                if L > cur:
                    return False  # 出现空档，无法全覆盖
                if R + 1 > cur:
                    cur = R + 1
                if cur > n:
                    return True
            return cur > n

        lo, hi = 0, n + m
        while lo < hi:
            mid = (lo + hi) // 2
            if ok(mid):
                hi = mid
            else:
                lo = mid + 1
        out_lines.append(str(lo))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    solve()

C++

// 一维网格染色传播 - 二分 + 预排序
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int64 n; int m;
        cin >> n >> m;
        vector<int64> a(m+1);
        for (int i = 1; i <= m; ++i) cin >> a[i];

        // 预处理：按 key = a_t + t 排序
        struct Node { int64 keyL, keyR; int t; };
        vector<Node> v; v.reserve(m);
        for (int i = 1; i <= m; ++i) {
            v.push_back(Node{a[i] + i, a[i] - i, i});
        }
        sort(v.begin(), v.end(), [](const Node& A, const Node& B){
            return A.keyL < B.keyL;
        });

        auto ok = [&](int64 TT)->bool{
            if (TT <= 0) return false;
            int64 cur = 1;
            for (auto &nd : v) {
                if (nd.t > TT) continue; // 尚未出现
                // L = (a_t + t) - TT, R = (a_t - t) + TT
                int64 L = nd.keyL - TT;
                int64 R = nd.keyR + TT;
                if (R < 1 || L > n) continue;
                if (L < 1) L = 1;
                if (R > n) R = n;
                if (L > cur) return false; // 出现空档
                if (R + 1 > cur) cur = R + 1;
                if (cur > n) return true;
            }
            return cur > n;
        };

        int64 lo = 0, hi = n + m;
        while (lo < hi) {
            int64 mid = (lo + hi) >> 1;
            if (ok(mid)) hi = mid;
            else lo = mid + 1;
        }
        cout << lo << "\n";
    }
    return 0;
}

---

Java

// 一维网格染色传播 - 二分 + 预排序
import java.io.*;
import java.util.*;

public class Main {
    static class Node {
        long keyL, keyR; // keyL = a_t + t, keyR = a_t - t
        int t;
        Node(long keyL, long keyR, int t){ this.keyL = keyL; this.keyR = keyR; this.t = t; }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        int T = Integer.parseInt(nextToken(br));
        while (T-- > 0) {
            long n = Long.parseLong(nextToken(br));
            int m = Integer.parseInt(nextToken(br));
            long[] a = new long[m+1];
            for (int i = 1; i <= m; i++) a[i] = Long.parseLong(nextToken(br));

            // 预处理：按 key = a_t + t 排序
            ArrayList<Node> v = new ArrayList<>(m);
            for (int i = 1; i <= m; i++) {
                v.add(new Node(a[i] + i, a[i] - i, i));
            }
            v.sort(Comparator.comparingLong(o -> o.keyL));

            // 判定函数：第 TT 秒结束时是否可全黑
            java.util.function.LongPredicate ok = (long TT) -> {
                if (TT <= 0) return false;
                long cur = 1;
                for (Node nd : v) {
                    if (nd.t > TT) continue; // 该源点尚未出现
                    long L = nd.keyL - TT;   // L = (a_t + t) - TT
                    long R = nd.keyR + TT;   // R = (a_t - t) + TT
                    if (R < 1 || L > n) continue; // 与 [1,n] 无交
                    if (L < 1) L = 1;
                    if (R > n) R = n;
                    if (L > cur) return false; // 出现空档
                    if (R + 1 > cur) cur = R + 1;
                    if (cur > n) return true;
                }
                return cur > n;
            };

            long lo = 0, hi = n + m;
            while (lo < hi) {
                long mid = (lo + hi) >>> 1;
                if (ok.test(mid)) hi = mid;
                else lo = mid + 1;
            }
            out.append(lo).append('\n');
        }
        System.out.print(out.toString());
    }

    // 朴素分词读取（基于 BufferedReader + 手动切分），兼顾可读性与性能
    static String nextToken(BufferedReader br) throws IOException {
        int c;
        StringBuilder sb = new StringBuilder();
        // 跳过空白
        while (true) {
            br.mark(1);
            c = br.read();
            if (c == -1) return sb.length() == 0 ? null : sb.toString();
            if (!Character.isWhitespace(c)) break;
        }
        // 读取 token
        while (c != -1 && !Character.isWhitespace(c)) {
            sb.append((char)c);
            br.mark(1);
            c = br.read();
        }
        return sb.toString();
    }
}

题目内容

有一条长度为$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$秒结束时全体网格变黑所需的最少秒数

样例1

输入

2
5 1 
3
10 2
2 9

输出

3
5

说明

初始全白。

对于样例一：

• 第$1$秒结束前手动将3染黑;
• 第$2$秒开始扩散为{$2,3,4$};
• 第3秒开始扩散为{$1,2,3,4,5$}，于是第$3$秒结束时全黑，答案为$3$。

对于样例二：

• 第2秒结束时黑格为{$1,2,3,9$};第$5$秒开始时两端扩散连通覆盖至全体，故第$5$秒结束时全黑,答案为$5$。