题目链接

整体思路：单调队列

思路

首先很显然的是答案情况一定会出现在长度最长的一行，所以输入的时候可以顺便求出最长的一行的长度 $sz$ 。

将两个光标之间的距离看作整体，第 $i - 1$ 行和第 $i$ 行之间的距离为 $a_i + 1$ ，所以在求出 $sz$ 之后可以顺便将 $a_i$ 全部 $+1$ 。

按顺序扔进队列使队列中元素的和始终小于等于 $sz$ ，最大的 $q.size() + 1$ 即为答案。

注意：要特判 $a_i > sz$ 时清空队列，不然会 $Subtask 1$ 最后一个点卡两个小时（感谢 sheep32768 神犇赛后帮我调出来了）。

AC 代码（STL 大法好！）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
const int N = 2e5 + 29;

int n, m, k;
int a[N];
queue<int> q;

void tbcsolve() {
    cin >> n;
    while (q.size()) q.pop();
    int sz = 0;
    rep (i, 1, n) {
        cin >> a[i];
        sz = max(sz, a[i]);
        a[i]++;
    }
    int ans = 1, sum = 0;
    rep (i, 2, n) {
        if (a[i] > sz) {
            while (q.size()) q.pop();
            sum = 0;
            continue;
        }
        if (a[i] + sum <= sz) {
            q.push(a[i]);
            sum += a[i];
            ans = max(ans, (int)q.size() + 1);
        }
        else {
            while (q.size() && a[i] + sum > sz) {
                sum -= q.front();
                q.pop();
            }
            sum += a[i];
            q.push(a[i]);
        }
    }
    cout << ans << endl;
}