B. Clockwork 题解

题意简述

有 $n$ 个时钟排成一行，第 $i$ 个时钟的初始时间为 $a_i$（$1 \le a_i \le 10^9$）。
每一秒按顺序发生：

1. 所有时钟时间减 $1$，若任一变为 $0$ 则立即失败。
2. 你可以移动到相邻时钟或停留。
3. 可将当前所在时钟重置为其初始值 $a_i$。

你可以从任意时钟开始，问是否存在一种策略使过程无限持续（永不失败）。

关键观察

• 每个时钟 $i$ 的时间每秒减少 $1$，必须在它变为 $0$ 之前到达并重置。
• 重置使该时钟时间恢复为 $a_i$，相当于“续命”。
• 移动一步需要 $1$ 秒，因此从某个时钟出发到达另一个时钟所需时间等于它们在序列上的距离。
• 要无限持续，每个时钟必须被周期性重置，且两次重置的时间间隔 $\le a_i$（否则中间会归零）。

转化为可行性条件

考虑最坏情况：你必须能够从最左端走到最右端并返回，且保证沿途所有时钟都不会归零。
对于位置 $i$（下标从 $0$ 开始），它到左端点的距离为 $i$，到右端点的距离为 $n-1-i$。
最危险的情况是：你需要从较远的端点出发，经过 $i$，再走到另一个端点。
从较远端到 $i$ 需要 $\max(i, n-1-i)$ 秒，此时 $i$ 的时间已减少这么多；重置后，你还要离开 $i$ 去往另一端点，这又需要 $\max(i, n-1-i)$ 秒，在这段时间内 $i$ 的时间会继续减少。
因此，为了保证 $i$ 在两次重置之间不会归零，必须满足：
$a_i > 2 \cdot \max(i, n-1-i)$。
由于 $a_i$ 是整数，等价于 $a_i \ge 2 \cdot \max(i, n-1-i) + 1$。

算法步骤

对于每个测试用例：

1. 读入 $n$ 和数组 $a$（下标 $0$ 到 $n-1$）。
2. 遍历 $i$，计算 $d = \max(i, n-1-i)$。
3. 若存在 $a_i \le 2d$，则输出 "NO"；否则输出 "YES"。

时间复杂度 $O(n)$，所有测试用例的 $n$ 总和不超过 $5 \times 10^5$，完全可行。

代码实现（标程）

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int T,n,i,t,flag;
    for(cin>>T;T>0;T--){
        cin>>n;
        flag=0;
        for(i=0;i<n;i++){
            cin>>t;
            if(t <= i*2 || t <= (n-i-1)*2) flag=1;
        }
        if(flag) cout<<"NO\n";
        else cout<<"YES\n";
    }
    return 0;
}

示例验证

以题目样例为例：

• $[4,10]$：$i=0$，$2\max(0,1)=2$，$4>2$ 通过；$i=1$，$2\max(1,0)=2$，$10>2$ 通过 → YES。
• $[2,2]$：$i=0$，$2\max(0,1)=2$，$2 \le 2$ 触发失败 → NO。
• $[4,10,5]$：$i=0$，$2\max(0,2)=4$，$4 \le 4$ 触发失败 → NO。
• $[5,3,5]$：$i=0$，$2\max(0,2)=4$，$5>4$；$i=1$，$2\max(1,1)=2$，$3>2$；$i=2$，$2\max(2,0)=4$，$5>4$ → YES。
• $[12,13,25,17,30]$：所有位置均满足 $a_i > 2\max(i,4-i)$ → YES。

与题目输出一致。

总结

本题核心是推导出每个时钟必须满足 $a_i > 2 \cdot \text{dist}_{\text{far}}(i)$，其中 $\text{dist}_{\text{far}}(i)$ 是 $i$ 到较远端的距离。贪心检查所有位置即可得到答案。