[蓝桥杯 2024 国 A] 最长子段
蓝桥补题 洛谷传送门
思路:将给出式子化为 sr - a*b*r > sl-1 - a*c*l ,需要找出满足最长r-l+1,可以维护sl数组最小前缀,sr数组最大后缀,然后二分长度O(n) check
需要注意边界情况,sr[n]的值不应与sr[n+1](也就是0 取最大
代码如下:
const int N=3e5+10,M=1e4+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
ll n;
ll s[N];
ll sl[N],sr[N];
void solve(){
ll a,b,c; cin >> n >> a >> b >> c;
for(int i=1;i<=n;i++) cin >> s[i],s[i]+=s[i-1];
for(int i=1;i<=n;i++) sl[i]=min(sl[i-1],s[i-1]-a*c*i);
sr[n]=s[n]-a*b*n;
for(int i=n-1;i;i--) sr[i]=max(sr[i+1],s[i]-a*b*i);
ll l=1,r=n;
ll ans=0;
while(l<=r){
ll mid=l+r>>1;
bool if1=0;
for(int i=1;i+mid-1<=n;i++) if(sr[i+mid-1]>sl[i]){if1=1; break;}
if(if1) ans=mid,l=mid+1;
else r=mid-1;
}
cout << ans;
}