洛谷 P16796 题解

· · 题解

传送门：P16796 [蓝桥杯 2026 国 B] 灯带修补
更佳的阅读体验：洛谷 P16796 题解

简要题意：给你一个环，你需要求出环上最长的连续子段，使得该字段中相邻元素之差的绝对值 > k 的位置数量 \le m。n \le 2 \times 10^5。

看到环，我们应该就有一个直觉是需要把整个序列在数组末尾再复制一次，这样环上问题就被转化成线性的序列问题了。

我们发现，最后的答案其实只和相邻元素之差的绝对值有关，而与 a_i 本身的值无关。此时，如果我们将 |a_i - a_{i + 1}| > k 视作 1，否则为 0，那我们就可以得到一个新的序列，即 d_i = \left [|a_i - a_{i + 1}| > k \right ]，其中 [P] 为条件表达式，命题 P 为真时值为 1，否则为 0。

这时，我们对序列 d 再做一次前缀和，我们就可以很简单地求出来每个区间有多少个位置符合条件了。那反过来想，其实只需要遍历一次序列 d，查找最后一个不超过 d_i + m 的位置即可。

时间复杂度 O(n \log n)。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;

const int N = 4e5 + 10;
int n, m, ans;
ll k, a[N], d[N];

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    copy(a + 1, a + n + 1, a + n + 1);
    for (int i = 1; i < (n << 1); ++i) d[i] = d[i - 1] + (abs(a[i] - a[i + 1]) > k);
    for (int i = 1; i <= n; ++i)
        ans = max(ans, min(n, int(upper_bound(d + 1, d + (n << 1) + 1, d[i] + m) - d - i)));
    cout << ans << '\n';
    return 0;
}