题目：传送门
思路：若存在答案 k , 那么一定有答案 m * k (其中m=1、2、3、...... 且 m * k <= n )，可推出 一定存在答案 k' > n/2 （后者是前者的必要条件）; 【显然 两个相邻长度为 k 的区间的和都>=0 ， 合并后也>=0;】
这道题的精髓也就在 不等式 k' > n/2 上。如果你对接下来的叙述有任何疑惑，请记住 k' > n/2 。
当 x >= 0 ， 对于任意左端点 L <= (n+1)/2 , 对应的长度为 k' 的区间 [ L , L + k' - 1 ] , 而 L + k' - 1 > (n+1)/2 （由 k' > n/2 得），故 L 对应的区间与最后的 [n/2] 相交，而 x >= 0 , 因此将右端点右移可使区间和变大，对于每个 L 对应的区间，右端点取到n可使区间和最大，那么只需要判断 [1,n] 的区间和即可 。 （最后[n/2] 个数字都是>=0 的，因此如果存在答案k --> k' > n/2， 那么 k'' = n 也应该同样满足; 后者是前者的必要条件）
当 x < 0 ， 对于任意左端点 L <= (n+1)/2 , 对应的长度为 k' 的区间 [ L , L + k' - 1 ] ， 若 区间和 sum <=0 , 那么就将其的右端点左移 （区间右边部分都是 x < 0），使其满足 sum > 0 。（双指针思想+贪心）那么可以设置 初始L = 1 和 初始答案 k = n , k越大，那么长度为k的区间数就越少（区间和的约束也就越少） ，且对于 区间[ L , L + k -1 ] ，其区间和若 > 0 ，那么 [ L , R ] 的区间和也 > 0 , (n+1)/2 < R < L + k -1 ，若区间和 < 0 , 则 k-- 。 对于 L = i 的对应的区间 ，当k--时 ， 则 L' < i 的区间长度也变短 ，其区间和减去一个负数，且之前已经处理过的L ' 对应的区间和是 > 0 的，那么减去负数也还是 > 0 。
一开始，发现 k 类似于一个多峰值函数，但采用一定贪心策略能够使其具有单调性，之后就可以用双指针求解了。至于快速获取区间和，可以先预处理前缀和。
#include<bits/stdc++.h> /* #include<cstdio> #include<cmath> #include<cstring> #include<vector> #include<cctype> #include<queue> #include<algorithm> #include<map> #include<set> */ #pragma GCC optimize(2) using namespace std; typedef long long LL; typedef pair<int,int> pii; typedef pair<double,double> pdd; const int N=1e6+5; const int M=1e4+5; const int inf=0x3f3f3f3f; const LL mod=1e9+7; const double eps=1e-9; const long double pi=acos(-1.0L); #define ls (i<<1) #define rs (i<<1|1) #define fi first #define se second #define pb push_back #define mk make_pair #define mem(a,b) memset(a,b,sizeof(a)) LL read() { LL x=0,t=1; char ch; while(!isdigit(ch=getchar())) if(ch=='-') t=-1; while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); } return x*t; } int a[N]; LL sum[N]; int main() { int n=read(); for(int i=1;i<=(n+1)/2;i++) a[i]=read(); int x=read(); for(int i=(n+1)/2+1;i<=n;i++) a[i]=x; for(int i=1;i<=n;i++) sum[i]=a[i]+sum[i-1]; if(x>=0) { if(sum[n]>0) printf("%d ",n); else printf("-1 "); return 0; } int len=n; for(int i=1;i<=n;i++) { int j=i+len-1; if(j>n||len<=n/2) break; LL t=sum[j]-sum[i-1]; while(t<=0&&len>n/2) t-=x,len--; } if(len<=n/2) printf("-1 "); else printf("%d ",len); return 0; }