D-切分数列（split）

题目背景

小 A 正在研究如何把一列数字合理地分组。

他希望把一个长度为 $n$ 的数列切成若干段，每一段都必须是 连续的一段 ，并且所有段都不能为空。为了让每一段的压力尽量均衡，他想让 每一段的元素和的最大值尽可能小 。

你的任务是帮助他求出这个最优值。

题目描述

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\dots,a_n$ ，请你将它划分成 恰好 $k$ 个非空连续子段 。

设这 $k$ 个子段的元素和分别为：

s_1,s_2,\dots,s_k

你需要最小化：

\max(s_1,s_2,\dots,s_k)

输出这个最小值。

输入格式

第一行输入两个整数 $n,k$ ，分别表示数列长度和需要划分的连续子段个数。

第二行输入 $n$ 个正整数 $a_1,a_2,\dots,a_n$ 。

输出格式

输出一个整数，表示把数列划分成恰好 $k$ 个非空连续子段后，各段元素和最大值的最小可能值。

输入输出样例

输入 #1

5 3
7 2 5 10 8

输出 #1

样例解释

一种最优划分方式是：

[7,2,5]\ [10]\ [8]

三段的段和分别为：

14,\ 10,\ 8

因此这一种划分下，最大段和为：

\max(14,10,8)=14

可以证明，不存在一种划分方案，使得最大段和小于 $14$ 。

数据范围

对于所有测试数据，保证：$1 \le k \le n \le 2 \times 10^5,\quad 1 \le a_i \le 10^9$

本题共设 $20$ 个测试点，各测试点满足的限制如下：

测试点编号	分值	$n$	$k$	特殊性质
$\text{1}$	$5$	$\le 10$	$=1$	$A$
$\text{2}$		$\le 10$	$=n$	$B$
$\text{3}$		$\le 20$	$\le n$	无特殊性质
$\text{4}$		$\le 20$	$\le n$	$C$
$\text{5}$		$\le 100$	$=1$	$A$
$\text{6}$		$\le 100$	$=n$	$B$
$\text{7}$		$\le 1000$	$\le n$	$D$
$\text{8}$		$\le 1000$	$\le n$	无特殊性质
$\text{9}$		$\le 2000$	$\le 10$	无特殊性质
$\text{10}$		$\le 5000$	$\le n$	$C$
$\text{11}$		$\le 10^4$	$\le n$	无特殊性质
$\text{12}$		$\le 2 \times 10^4$	$\le 20$	无特殊性质
$\text{13}$		$\le 5 \times 10^4$	$\le n$	$E$
$\text{14}$		$\le 8 \times 10^4$	$\le n$	无特殊性质
$\text{15}$		$\le 10^5$	$\le 100$	无特殊性质
$\text{16}$		$\le 1.2 \times 10^5$	$\le n$	$D$
$\text{17}$		$\le 1.5 \times 10^5$		无特殊性质
$\text{18}$		$\le 1.8 \times 10^5$		$E$
$\text{19}$		$\le 2 \times 10^5$	$=1$ 或 $=n$	$A$ 或 $B$
$\text{20}$		$\le 2 \times 10^5$	$\le n$	无特殊性质

特殊性质 $A$ ：保证 $k=1$ 。

特殊性质 $B$ ：保证 $k=n$ 。

特殊性质 $C$ ：保证数列单调不降，即对任意 $1 \le i < n$ ，都有 $a_i \le a_{i+1}$ 。

特殊性质 $D$ ：保证所有 $a_i$ 相等。

特殊性质 $E$ ：保证 $a_i \le 1000$ 。

Overview

ID 453

类型传统题

Time Limit 1000ms

Memory Limit 256MiB

Stats

尝试 13

已通过 7

难度 5

上传者

_Separation

标签

在下列比赛中:

「果壳杯」 ROUND 44 (Div. 4)