AT_abc370_f [ABC370F] Cake Division

题目描述

有一个圆形蛋糕，被切成了 $N$ 块，每一刀都是从圆心到圆弧上的某一点。

每一块蛋糕和每一道切口都按顺时针方向编号为 $1, 2, \ldots, N$，第 $i$ 块蛋糕的质量为 $A_i$。我们也把第 $1$ 块蛋糕称作第 $N+1$ 块。

第 $i$ 道切口位于第 $i$ 块和第 $i+1$ 块蛋糕之间，顺时针顺序为：第 $1$ 块蛋糕、切口 $1$、第 $2$ 块蛋糕、切口 $2$、……、第 $N$ 块蛋糕、切口 $N$。

现在要将这个蛋糕分给 $K$ 个人，分配需要满足以下条件。设第 $i$ 个人获得的蛋糕总质量为 $w_i$。

• 每个人都必须获得至少一块连续的蛋糕。
• 没有任何一块蛋糕会被遗漏。
• 在满足上述两个条件的前提下，使 $\min(w_1, w_2, \ldots, w_K)$ 的值最大。

请你求出满足条件的分法中，$\min(w_1, w_2, \ldots, w_K)$ 的最大值 $x$，以及在所有满足条件的分法中，切口没有被切开的切口数 $y$。这里，切口 $i$ 被切开是指第 $i$ 块和第 $i+1$ 块蛋糕被分给了不同的人。

输入格式

输入为标准输入，格式如下：

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出满足条件的分法中，$\min(w_1, w_2, \ldots, w_K)$ 的最大值 $x$，以及在所有满足条件的分法中，切口没有被切开的切口数 $y$，用空格隔开。

输入输出样例 #1

输入 #1

5 2
3 6 8 6 4

输出 #1

13 1

输入输出样例 #2

输入 #2

6 3
4 7 11 3 9 2

输出 #2

11 1

输入输出样例 #3

输入 #3

10 3
2 9 8 1 7 9 1 3 5 8

输出 #3

17 4

说明/提示

限制条件

• $2 \leq K \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^4$
• 所有输入均为整数

样例解释 1

以下分法满足条件：

• 一个人获得第 $2, 3$ 块，另一个人获得第 $4, 5, 1$ 块。第 $2, 3$ 块的质量和为 $14$，第 $4, 5, 1$ 块的质量和为 $13$。
• 一个人获得第 $3, 4$ 块，另一个人获得第 $5, 1, 2$ 块。第 $3, 4$ 块的质量和为 $14$，第 $5, 1, 2$ 块的质量和为 $13$。 满足条件的分法中，$\min(w_1, w_2)$ 的最大值为 $13$，且无论哪种分法，只有切口 $5$ 没有被切开，因此答案为 $13\ 1$。

由 ChatGPT 4.1 翻译