E. Are You Fired?(贪心&分类）

传送门

思路：首先要知道 $k>\dfrac{n}{2}$ ，因为假设 $k\leq\dfrac{n}{2}$ 满足条件，那么 $2k$ 也显然满足。

接下来对 $x$ 正负进行讨论，

$pos1:x\geq0$ ，只需对 $k=n$ 进行判断。如果 $pre[n]>0$ 则输出 $n$ ，反之不成立。

$pos2:x<0$ ,

因为要满足 $\forall i\in[0,n-k]\rightarrow pre[i+k]-pre[i]>0$

因为 $k>\dfrac{n}{2}$ ，所以区间右端肯定包含 $x$ 。

因此 $pre[i+k]=pre[n]-x\times(n-k-i)$

将含 $i$ 的项移到一边： $pre[i]-ix<pre[n]-(n-k)x$

因为 $pre[n]-(n-k)x=pre[k]$

所以最终等式为 $pre[i]-ix<pre[k],i\in[0,n-k]$

只需让 $(pre[i]-ix)_{max}<pre[k]$ 即可。

因为 $n-k$ 最大为 $n-\dfrac{n+1}{2}$ ，所以可以递推得到左边所有的最值。

时间复杂度： $O(n)$

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
#define mst(a) memset(a,0,sizeof a)
ll a[N],pre[N],mx[N]; 
int main(){
    int n,x,m,ok=0;
    scanf("%d",&n);
    m=(n+1)/2;
    for(int i=1;i<=m;i++) scanf("%lld",&pre[i]),pre[i]+=pre[i-1];
    scanf("%d",&x);
    for(int i=m+1;i<=n;i++) pre[i]=pre[i-1]+x;
    for(int i=1;i<=m;i++) mx[i]=max(mx[i-1],pre[i]-1LL*i*x);
    if(pre[n]>0) printf("%d\n",n),ok=1;
    else if(x>=0) puts("-1"),ok=1;
    if(ok) return 0;
    for(int k=m;k<=n;k++){
        if(mx[n-k]<pre[k]){
            printf("%d\n",k);
            return 0;
        }
    }
    puts("-1");
    return 0;
}