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

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

传送门

思路：首先要知道，因为假设满足条件，那么也显然满足。

接下来对正负进行讨论，

，只需对进行判断。如果则输出，反之不成立。

,

因为要满足

因为，所以区间右端肯定包含。

因此

将含的项移到一边：

因为

所以最终等式为

只需让即可。

因为最大为，所以可以递推得到左边所有的最值。

时间复杂度：

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;
}