题解：CF1358E Are You Fired?

yingkeqian9217 · 2025-04-11 09:38:51 · 题解

这里说一下不用分类讨论的简单做法。

注意到若 k 合法，则 2k(2k<n) 也合法，故若有解则一定存在 k>\lceil \frac{n}{2}\rceil 合法。

记 m=\lceil \frac{n}{2}\rceil，后缀和数组 suf_i=\sum_{j=i}^m a_j，即要求 \min_{i=1}^{n-k+1}suf_i+(i+k-m-1)x>0，参变分离即为 suf_i+ix 的前缀最小值。

#include<bits/stdc++.h>
#define maxn 510005
#define int long long
using namespace std;
int n,m,x,a[maxn];
signed main(){
    scanf("%lld",&n),m=(n+1>>1);
    for(int i=1;i<=m;i++) scanf("%lld",&a[i]);
    scanf("%lld",&x);
    for(int i=m;i>=1;i--) a[i]+=a[i+1];
    int minn=1e18;
    for(int i=1;i<=m;i++){
        minn=min(minn,a[i]+x*i);
        if(minn+(n-m-i)*x>0) return printf("%lld\n",n-i+1),void();
    }
    puts("-1");
    return 0;
}