天眼查询企业信息电话_律师网站建设费用_靠谱的拉新平台_百度推广个人怎么开户

蓝桥补题                                                         洛谷传送门

思路:将给出式子化为 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;
}