当前位置: 首页 > article >正文

[蓝桥杯 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;
}


http://www.kler.cn/a/589751.html

相关文章:

  • 虚幻基础:GAS
  • 2.4 python网络编程
  • Matlab 单球机器人动力学与LQR控制研究
  • 2025年03月11日Github流行趋势
  • 深入理解C++编程:从内存管理到多态与算法实现
  • 国密系列加密技术及其在爬虫逆向中的应用研究
  • JDK15开始偏向锁不再默认开启
  • 求职招聘网站源码,找工作招工系统,支持H5和各种小程序
  • 13个问题
  • Java概述
  • Ubuntu22.04虚拟机里安装Yolov8流程
  • Oracle GoldenGate (OGG) 安装、使用及常见故障处理
  • SpringBoot集成ElasticSearch实现支持错别字检索和关键字高亮的模糊查询
  • 分治(2)——快速搜索算法
  • 51单片机学习记录
  • 时间序列分析的军火库:AutoTS、Darts、Kats、PaddleTS、tfts 和 FancyTS解析
  • 【小项目】四连杆机构的Python运动学求解和MATLAB图形仿真
  • 机器学习--卷积神经网络原理及MATLAB回归实现
  • Docker 使用指南
  • C# WPF编程-画刷(Brush)填充图形对象的颜色或图案