题解：CF1616D Keep the Average High

TCY1234567 · 2026-06-10 19:59:33 · 题解

题解

首先有一个较为显然的转化，就是将 b_i 减 x，这样问题就变成了 \sum_{i = l}^{r} b_i \ge 0。

直接枚举肯定不可取，我们考虑发现一些性质。我们首先应该想如何去判断选出的合不合法，我们依据裴蜀定理可得，这些大于 1 的长度均可以用 2 和 3 表示。这样这个问题就得到了简化。

接着我们考虑，如果新加进来一个数，我们该如何维护，它又会产生什么贡献。

考虑不合法有什么情况。

对于长度为 2 的来说，加进去当前的数如果和上一个数相加小于 0，证明其不合法。

对于长度为 3 的同理，只需判断 a_i+a_{i-1}+a_{i-2} 是否小于 0 即可，正确性显然。

为了方便维护，直接将不合法的 a_i 设成正无穷即可，这样不会影响后续结果。

代码

#include <bits/stdc++.h>
using namespace std;
int a[50005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        int x;
        scanf("%d",&x);
        for(int i=1;i<=n;i++) a[i]-=x;
        int ans = n;
        for(int i=2;i<=n;i++)
        {
            if(a[i]+a[i-1]<0||a[i]+a[i-1]+a[i-2]<0)
            {
                ans--;
                a[i] = 0x3f3f3f3f;
            }
        }
        printf("%d\n",ans);
    }
}