CF2026B Black Cells 题解

Goodans · 2024-11-12 16:19:18 · 题解

解题思路

基本观察：

要使 k 较小，我们只能涂染那些距离比较近的单元格。要求每两个单元格之间的距离不超过 k，求 k 的最小值。

策略：

计算最小的 k：遍历 a 中的值，计算每两个相邻单元格的间隔。

代码：

import sys
INF = 10**18

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    if n == 1:
        print(1) #因为n==1时，只有一个数据，直接输出。
    elif n % 2 == 1:
        ans = INF
        for i in range(1, n + 1, 2):
            mx = 0
            for j in range(1, i, 2):
                mxx = max(mxx, a[j] - a[j - 1])
            for j in range(i + 1, n, 2):
                mxx = max(mxx, a[j] - a[j - 1])
            ans = min(ans, mxx)

        print(max(1, ans))
    else:
        mxx = 0
        for i in range(1, n, 2):
            mxx = max(mxx, a[i] - a[i - 1])
        print(mxx)

def main():
    T = int(input())
    for _ in range(T):
        solve()

if __name__ == "__main__":
    main()