#P3649. 第3题-网格染色
          
                        
                                    
                      
        
              - 
          
          
                      1000ms
            
          
                      Tried: 36
            Accepted: 6
            Difficulty: 6
            
          
          
          
                       所属公司 : 
                              阿里
                                
            
                        
              时间 :2025年9月11日-阿里云算法岗
                              
                      
          
 
- 
                        算法标签>二分算法          
 
第3题-网格染色
解题思路
模型重述
把每次“手动染黑”看成在时间点 t 出现的一个“源点” a_t。
第 t+1, t+2, … 秒的开始,这个源点会以每秒 1 格的速度向左右扩散。因此,到第 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≤T 的源点区间,按左端点从小到大排序,线性扫描合并并检查能否无缝覆盖 [1,n] 即可。
小优化(预排序 O(1) 次、判定 O(m)): 注意左端点
Lt=at−(T−t)=(at+t)−T对同一组数据来说,(at+t) 是与 T 无关的常数。因此我们可以预先按键 key = a_t + t 将所有源点排序一次;之后每次判定只需按这个固定顺序遍历(过滤掉 t > T 的源点),计算对应区间并线性扫一遍即可,无需每次再排序。
二分边界
- 下界 
lo = 0(显然不可能,但便于统一写法)。 - 上界 
hi = n + m:最多等到所有手动染色都发生(m秒),再向最远端扩散不超过n秒,必定覆盖。 
整体就成了:在 [0, n+m] 上二分最小的可行 T。
复杂度分析
- 预排序一次:O(mlogm)。
 - 每次判定:线性 O(m)。
 - 二分次数:⌈log2(n+m+1)⌉≤40(因 n≤109)。
 - 总体:O(mlogm+mlog(n+m))。题目保证单测文件内 ∑m≤2×105,完全可过。
 
代码实现
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秒,每一秒结束前会给出一个整数at,表示将编号为at的网格手动染成黑色。
同时,过程按秒进行、且在m秒之后也继续进行:在每一秒开始时,所有已经为黑色的网格会同时将其左右相邻(编号相差为1)的白色网格染成黑色(若相邻位置不存在则忽略)。
请计算:最少经过多少秒结束时,所有网格都被染成黑色。
- 
更明确的时间线(同一秒内按如下顺序执行):
- 在第t秒开始时,所有黑色网格同时向左右各扩散1格,将相邻白色网格染黑;
 - 若t≦m,则在第t秒结束前,额外将编号为at的网格手动染黑(若已为黑色则无额外影响)。
 
 - 
在t>m时不再有手动染色,但“每秒开始时的扩散”仍持续进行,直到全体网格变黑为止。
 
你需要输出满足“在第t秒结束时全黑”的最小t。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦104)代表数据组数,每组测试数据描述如下:
第一行输入两个整数n,m(1≦n≦109;1≦m≦2×105)表示网格长度与手动染色的次数;
第二行输入m个整数a1,a2,...,am(1≦ai≦n)表示第t秒结束前手动染黑的网格编号。
除此之外,保证单个测试文件的m之和不超过2×105。
输出描述
对于每一组测试数据,新起一行,输出一个整数,表示在第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。