题解：AT_abc032_c [ABC032C] 列

残阳如血 · 2025-02-08 08:23:57 · 题解

\textbf{Solution}

双指针。

首先先判一个特殊情况：若序列中存在 0，由于 k\ge 0，则答案必然为 n。

用双指针 i,j 维护区间 [i,j]，s 统计区间所有元素的积，跑一遍板子就行了。

注意，当 i 移出区间时，只有 j\ge i（即当前区间存在）才要除以 a_i。

\textbf{Code}

record。

#include <bits/stdc++.h>
using lint = long long;
const int N = 1e5 + 10;

int n, len;
lint k, s = 1, a[N];

int main() {
    std::cin >> n >> k;
    for (int i = 1; i <= n; ++i) std::cin >> a[i];
    for (int i = 1; i <= n; ++i)
        if (!a[i]) return std::cout << n << std::endl, 0;

    for (int i = 1, j = 0; i <= n && j <= n; ++i) {
        while (j < n && s * a[j + 1] <= k) s *= a[++j];
        len = std::max(len, j - i + 1);
        if (j >= i) s /= a[i];
    }
    std::cout << len << std::endl;
    return 0;
}