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

洛谷 P1182 数列分段 Section II 二分详细讲解

根据题意可以看出,我们二分的,每段和的最大值的,左边界为数组中最大的一个数,右边界为所有数之和。

我们可以二分这个每段和的最大值,找出满足m段的最小值

根据图来理解代码的注解



const int N = 1e5 + 10;


int n,m;
int a[N];

bool check(int x)
{
	int cnt = 0,sum = 0;//段数,每段的总和
	for (int i = 1;i <= n;i ++)
	{
		if (sum + a[i] <= x) sum += a[i];
		else cnt ++,sum = a[i];
	}
	cnt ++;//记录最后一段
	return cnt > m;//段数>m,说明当前这个最大值偏小
}

void solve()
{
	cin >> n >> m;
	int maxn = 0,sum = 0;
	for (int i = 1;i <= n;i ++) 
		cin >> a[i],maxn = max(maxn,a[i]),sum += a[i];
	
	int l = maxn - 1,r = sum + 1;//根据题意可以看出,左边界为maxn,右边界为sum。这样写是为了将取值范围扩大,避免边界出错
	while(l + 1 != r)
	{
		int mid = l + r >> 1;//二分最大值
		if (check(mid)) l = mid;//mid偏小
		else r = mid;
	}


	cout << r << endl;//输出边界线的右边

	
		
} 




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

相关文章:

  • vue3vue-elementPlus-admin框架中form组件的upload写法
  • 人工智能辅助 3D 建模:Claude + Blender MCP 体验
  • Java高频面试之集合-13
  • vllm-openai多服务器集群部署AI模型
  • 365天之第P10周:Pytorch实现车牌识别
  • [HelloCTF]PHPinclude-labs超详细WP-Level 0
  • 本地部署 RAGFlow - 修改默认端口
  • 【npm ERR! code ERESOLVE npm ERR! ERESOLVE unable to resolve dependency tree】
  • 论文阅读:2023-arxiv Can AI-Generated Text be Reliably Detected?
  • 重构版:JavaScript 的 new 操作符——从“黑箱仪式”到“亲手造物”的认知跃迁
  • 大语言模型入门文献推荐
  • 多模态模型Orpheus,基于病理图像的乳腺癌复发风险智能评估工具|顶刊解读·25-03-17
  • Oracle 查询表占用空间(表大小)的方法
  • 设计模式-组件协作
  • 问题链的拓扑学重构
  • java 动态赋值写入word模板
  • react实现虚拟列表
  • MYsql—1
  • 【Linux系统】进程地址空间详解
  • GLOW-TTS