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

【洛谷 P1182】数列分段 Section II 题解(二分答案+循环)

数列分段 Section II

题目描述

对于给定的一个长度为N的正整数数列 A 1 ∼ N A_{1\sim N} A1N,现要将其分成 M M M M ≤ N M\leq N MN)段,并要求每段连续,且每段和的最大值最小。

关于最大值最小:

例如一数列 4   2   4   5   1 4\ 2\ 4\ 5\ 1 4 2 4 5 1 要分成 3 3 3 段。

将其如下分段:

[ 4   2 ] [ 4   5 ] [ 1 ] [4\ 2][4\ 5][1] [4 2][4 5][1]

第一段和为 6 6 6,第 2 2 2 段和为 9 9 9,第 3 3 3 段和为 1 1 1,和最大值为 9 9 9

将其如下分段:

[ 4 ] [ 2   4 ] [ 5   1 ] [4][2\ 4][5\ 1] [4][2 4][5 1]

第一段和为 4 4 4,第 2 2 2 段和为 6 6 6,第 3 3 3 段和为 6 6 6,和最大值为 6 6 6

并且无论如何分段,最大值不会小于 6 6 6

所以可以得到要将数列 4   2   4   5   1 4\ 2\ 4\ 5\ 1 4 2 4 5 1 要分成 3 3 3 段,每段和的最大值最小为 6 6 6

输入格式

1 1 1 行包含两个正整数 N , M N,M N,M

2 2 2 行包含 N N N 个空格隔开的非负整数 A i A_i Ai,含义如题目所述。

输出格式

一个正整数,即每段和最大值最小为多少。

样例 #1

样例输入 #1

5 3
4 2 4 5 1

样例输出 #1

6

提示

对于 20 % 20\% 20% 的数据, N ≤ 10 N\leq 10 N10

对于 40 % 40\% 40% 的数据, N ≤ 1000 N\leq 1000 N1000

对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 1 0 5 1\leq N\leq 10^5 1N105 M ≤ N M\leq N MN A i < 1 0 8 A_i < 10^8 Ai<108, 答案不超过 1 0 9 10^9 109


思路

函数check用来判断当前的x是否满足条件。在函数check中,会遍历数列a[N],将当前位置的数加到sum上,并判断sum是否超过x。如果超过x,则创建新区间,将sum重新赋值为当前位置的数,并将cnt加1。最后,返回cnt是否大于m。

首先读入n和m的值,然后读入数列a[N]的值,并初始化l和r的值。因为所有元素都要划入区间内,所以要保证最大的元素也要被划进某一个区间,l初始化为数列a[N]中的最大值。如果把所有元素都划进区间,那么区间的最大值肯定不会超过所有元素的和,r初始化为数列a[N]中所有数的和。

使用二分法来寻找满足条件的x。在每一次循环中,计算mid的值,并调用check函数判断是否满足条件。如果满足条件,则说明x偏小,将l更新为mid+1。如果不满足条件,则说明x偏大,将r更新为mid-1。

注意:check函数中,需要将区间数cnt初始化为1,因为最少有一个区间。


AC代码

#include <algorithm>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;

const int N = 1e6 + 7;

int n, m;
int a[N];

bool check(int x) {
	int sum = 0;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		int tmp = sum + a[i];
		if (tmp > x) {
			sum = a[i];
			cnt++;
		} else {
			sum = tmp;
		}
	}
	// cout << x << " " << cnt << endl;
	return cnt >= m;
}

int main() {
	int l, r, mid;
	l = 0;
	r = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		l = max(l, a[i]);
		r += a[i];
	}
	while (l <= r) {
		mid = (l + r) >> 1;
		if (check(mid)) {
			// 偏小
			l = mid + 1;
		} else {
			// 偏大
			r = mid - 1;
		}
	}
	cout << l << endl;
	return 0;
}

http://www.kler.cn/news/134140.html

相关文章:

  • WSL 2 更改默认安装的 Linux 发行版
  • 基于单片机C51全自动洗衣机仿真设计
  • 异常语法详解
  • 飞鼠异地组网工具实战之访问k8s集群内部服务
  • 如何在虚拟机的Ubuntu22.04中设置静态IP地址
  • Vue3+ElementPlus纯前端分页(手撕分页),无需修改后端
  • 全新云开发工具箱:融合多项功能的微信小程序源码解决方案
  • 深眸科技革新升级OCR技术,与AI视觉实现有效融合赋能各行业应用
  • 选择最适合你的框架和语言,打造出色的Windows界面程序
  • Java学习笔记43——函数式接口
  • C++多线程编程(1):线程的创建方式
  • Node.js之TCP(net)
  • python 词云 wordcloud使用paddle模式 庆余年人物分析--不是特别准,可以看着玩一玩
  • 基于深度学习的单帧图像超分辨率重建综述
  • Postman接收列表、数组参数@RequestParam List<String> ids
  • C练习题_13
  • Zabbix实现故障自愈
  • rabbitmq默认交换机锁绑定的routingkey-待研究
  • ICASSP2023年SPGC多语言AD检测的论文总结
  • 算法设计与分析复习--贪心(二)
  • 开源更安全? yum源配置/rpm 什么是SSH?
  • yolov5模型代码怎么修改
  • Cesium+Vue:地形开挖
  • Ps:变换
  • 应用协议安全:Rsync-common 未授权访问.
  • Vue3+Vite实现工程化,事件绑定以及修饰符
  • C# GC机制
  • aspose.cells java合并多个excel
  • SpringCloud微服务注册中心:Nacos介绍,微服务注册,Ribbon通信,Ribbon负载均衡,Nacos配置管理详细介绍
  • 【算法】树形DP③ 监控二叉树 ⭐(二叉树染色二叉树灯饰)!