CF1616D

activeO · 2022-01-03 14:05:00 · 题解

题目大意

给一个数组，让你选择数组中的最大元素数，使得任意一段区间 [l,r] 满足：

思路

将 a_i \gets a_i-x (i \in [1,n]) ，这样就只要满足 a_l + a_{l+1} + ... + a_{r} \geq 0 。

对于 a_i (i \in [2,n]) ，如果 a_i+a_{i-1}+a_{i-2} < 0 \&\& a_i+a_{i-1} < 0 ，显然就不会选 a_i 了，那么我们就 a_i \gets +\infty 。

代码

#include <bits/stdc++.h>//祝大家学习愉快！

using namespace std;

const int maxn=5e4+10;
const int inf=0x3f3f3f3f;
int a[maxn];

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 ans=n,x;
        scanf("%d",&x);
        for(int i=1;i<=n;i++) a[i]-=x;
        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]=inf;
            }
        }
        printf("%d\n",ans);
    }

    return 0;
}