牛客练习赛158
小雷姆吃大餐官方中文
题目描述
官方中文小老鼠雷姆悄悄潜入了对面的野区…… 野区中有 $n$ 只野怪，给定长为 $n$ 的数组 $a_1,a_2,\dots,a_n$，表示击杀第 $i$ 只野怪会耗时 $a_i$。雷姆必须按顺序击杀所有野怪，且不能分多次击杀同一只野怪。 为了不被对面的灵魅发现，雷姆需要将这些野怪拆成恰好 $k$ 组来偷吃。每组必须是原顺序中连续的一段，且至少包含 $1$ 只野怪，每只野怪恰好属于一组。 对每组野怪，雷姆可以召唤一次他的小小帮手，立即击杀其中的一只野怪。每组的总耗时为除了小小帮手击杀的野怪外，该组中其他野怪的击杀耗时之和。 现在雷姆想求出各组总耗时最大值的最小可能值。由于雷姆还在呼呼大睡！所以这个问题需要你来回答。官方中文
输入格式
官方中文第一行包含两个整数 $n,k\left(1\le k\le n\le 2\times10^5\right)$，表示野怪的数量、需要划分的组数。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n\left(1\le a_i\le10^9\right)$，其中 $a_i$ 表示雷姆击杀第 $i$ 只野怪需要的时间。官方中文
输出格式
官方中文输出一个整数，表示各组总耗时最大值的最小可能值。官方中文
样例
Input #1
6 2
10 9 8 1 1 1Output #1
9将野怪分成以下两组：
$\hspace{23pt}\bullet\,$第一组包含第 $1,2$ 只野怪，让小小帮手击杀第 $1$ 只野怪，该组总耗时为 $9$;
$\hspace{23pt}\bullet\,$第二组包含第 $3,4,5,6$只野怪，让小小帮手击杀第 $3$ 只野怪，该组总耗时为 $1+1+1=3$。
两组总耗时的最大值为 $9$，可以证明不存在更优的方案。
题目信息
题面与样例版权归 牛客竞赛 及出题人所有；中文翻译由 AI 生成（官方原文），如有出入请以原文为准。