数列分段 Section II

这篇具有很好参考价值的文章主要介绍了数列分段 Section II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数列分段 Section II

题目描述

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

关于最大值最小:

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

将其如下分段:

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

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

将其如下分段:

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

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

5 3
4 2 4 5 1

样例输出 #1

6

提示

对于 \(20\%\) 的数据,\(N\leq 10\)

对于 \(40\%\) 的数据,\(N\leq 1000\)

对于 \(100\%\) 的数据,\(1\leq N\leq 10^5\)\(M\leq N\)\(A_i < 10^8\), 答案不超过 \(10^9\)

解析&代码

二分答案

先介绍下二分答案吧

比如我们要从一本英汉词典上查一个单词,如果你从头到尾一页一页的翻着找(并仔细一点),这样找可以保证一定能找到,但是最坏情况你要把整本词典都翻一遍,那就麻烦了(而且很累)。

有什么改进的方法吗?当然有。

我们考虑把这个词典从中间分开,看一下中间那一页的主要单词都是啥,然后去判断我要找的单词应该在左半部分还是右半部分,再去那一部分考虑怎么找就好了。同样的,在另一部分也是要进行划分并且判断的操作。这样一直进行下去,便能很快的找到答案,而且根本不需要翻过整个词典来。

可以证明,如果一页一页的找,最多要找 \(n\) 次,但是用这个方法,最多找\(floor(log2n)\)次。

我们把这个方法叫做“二分答案”。顾名思义,它用二分的方法枚举答案,并且枚举时判断这个答案是否可行。但是,二分并不是在所有情况下都是可用的,使用二分需要满足两个条件:

  1. 有上下界

  2. 区间有单调性

二分答案应该是在一个单调闭区间上进行的。也就是说,二分答案最后得到的答案应该是一个确定值,而不是像搜索那样会出现多解。二分一般用来解决最优解问题。刚才我们说单调性,那么这个单调性应该体现在哪里呢?

可以这样想,在一个区间上,有很多数,这些数可能是我们这些问题的解,换句话说,这里有很多不合法的解,也有很多合法的解。我们只考虑合法解,并称之为可行解。考虑所有可行解,我们肯定是要从这些可行解中找到一个最好的作为我们的答案, 这个答案我们称之为最优解。

最优解一定可行,但可行解不一定最优。我们假设整个序列具有单调性,且一个数x为可行解,那么一般的,所有的 \(x'(x'<x)\) 都是可行解。并且,如果有一个数y是非法解,那么一般的,所有的 \(y'(y'>y)\) 都是非法解。

那么什么时候适用二分答案呢?注意到题面:使得选手们在比赛过程中的最短跳跃距离尽可能长。如果题目规定了有“最大值最小”或者“最小值最大”的东西,那么这个东西应该就满足二分答案的有界性(显然)和单调性(能看出来)。

所以(快点)上代码吧。。。文章来源地址https://www.toymoban.com/news/detail-514551.html

#include <bits/stdc++.h>
using namespace std;
int n,m,a[100010],l,r;
int f(int x)
{
	int ret=0,last=0;
	for(int i=1;i<=n;i++)
	{
		if(last+a[i]<=x)
		{
			last+=a[i];
		}
		else{
			ret++;
			last=a[i];
		} 
	}
	return ret;
}
int main()
{
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	for(int i=1;i<=n;i++)
	{
	 	l=max(l,a[i]);
		r+=a[i];
	}
	while(l<r)
	{
		int mid=(l+r)/2;
		if(f(mid)>=m)
		{
			l=mid+1;
		}
		else{
			r=mid;
		}
	}
	cout << l;
	return 0;
}

到了这里,关于数列分段 Section II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】446. 等差数列划分II -- 子序列

    题目链接 我们要知道以某个位置为结尾的子序列的数量,可以通过它的以上一位置的为结尾的子序列的数量得知,也就是说,这是一个dp问题。 dp问题我们需要创建dp表,如果我们单纯使用dp[i]来表示以 i 位置为结尾的子序列的数量是完全不够的。因为我们不知道以 i-1 位置为

    2024年02月14日
    浏览(53)
  • 【动态规划】C++算法:446等差数列划分 II - 子序列

    视频算法专题 动态规划汇总 给你一个整数数组 nums ,返回 nums 中所有 等差子序列 的数目。 如果一个序列中 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该序列为等差序列。 例如,[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。 再例如,[1, 1, 2, 5, 7] 不是

    2024年02月03日
    浏览(39)
  • 【LInux】进程概念II -- 描述进程

    Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法…感兴趣就关注我吧!你定不会失望。 在初学阶段,我们对进程这个词仅在书上看见过,大多不太理解这个究竟是什么意思? 回顾我们之前所讲,如何去管理一件事物: 先描述再组织 .同样的 操作系统想要对进程进行管理也

    2024年02月07日
    浏览(40)
  • C++力扣题目216--组合求和II

    力扣题目链接(opens new window) 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。 说明: 所有数字都是正整数。 解集不能包含重复的组合。 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]] 示例 2: 输入: k = 3, n = 9 输出: [[1,2,6]

    2024年01月17日
    浏览(45)
  • 某软件的一个模块的需求规格说明书中描述【软件测试题目】

    某软件的一个模块的需求规格说明书中描述 (1)年薪制员工:严重过失,扣年终风险金的4%;过失,扣年终风险金的2% (2)非年薪制员工:严重过失,扣除当月薪资的8%;过失,扣除当月薪资的4% (1)分析原因及结果 原因 c1:年薪制员工 c2:非年薪制员工 c3:过失 c4:严重过失

    2024年02月08日
    浏览(50)
  • 二叉树题目:二叉树的层序遍历 II

    标题:二叉树的层序遍历 II 出处:107. 二叉树的层序遍历 II 4 级 要求 给你二叉树的根结点 root texttt{root} root ,返回其结点值自底向上的层序遍历(即从左到右,按从叶结点所在层到根结点所在层逐层遍历)。 示例 示例 1: 输入: root   =   [3,9,20,null,null,15,7] texttt{root = [3

    2024年02月11日
    浏览(38)
  • 数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)

    目录 题目描述 输入示例 输出示例 解题思路  解题方法(C语言) 解析 有序的二叉树遍历可以用堆栈以非递归的方式实现。 例如: 假设遍历一个节点数为6的二叉树(节点数据分别为1到6)时, 堆栈操作为:push(1);push(2);push(3);pop();pop();push(4);pop()

    2024年02月07日
    浏览(50)
  • 【十九】【动态规划】518. 零钱兑换 II、279. 完全平方数、474. 一和零,三道题目深度解析

    动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重

    2024年02月03日
    浏览(41)
  • 【四】【C语言\动态规划】地下城游戏、按摩师、打家劫舍 II,三道题目深度解析

    动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重

    2024年02月04日
    浏览(46)
  • 【LeetCode题目详解】 977.有序数组的平方 209.长度最小的子数组59.螺旋矩阵II day2

    看完这个题目第一想法就是直接暴力解决,直接将全部平方然后进行排序。比如快排。 代码如下: 时间复杂度是 O(nlogn)或者说【O(n + nlogn)】,括号里面这个是为了比较接下来的方法。 然后看了代码随想录的视频学习了用双指针来写这道题的方法(说实话不看视频真没想到可

    2024年02月13日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包