#P3929. [Seerc2014]Circle of digits

    ID: 3131 传统题 1000ms 128MiB 尝试: 62 已通过: 8 难度: 8 上传者: 标签>CF2400提高+/省选-有限候选集缩减复制数组处理环后缀数组LCP+RMQST 表二分答案贪心保持领先暴力枚举倍增计数排序

[Seerc2014]Circle of digits

题目描述

给定一个长为 nn 的环形字符串,仅包含数字 11 到 99。将其分成 kk 个部分,要求分出来的 kk 个数字,最大值最小化。

输入格式

输入的第一行包含两个整数 n,kn,k,意义见题目描述。 输入的第二行包含一个字符串,从一个字符出发,绕题目描述中的环形字符串一周后得到的字符串。

输出格式

输出一个整数,为最大值的最小可能值。

4 2
4321
32
7 3
7654321
176
5 5
12321
3

样例说明

对于第一个样例,最优的划分是 {32,14}\{\texttt{32},\texttt{14}\}; 对于第二个样例,最优的划分是 {176,54,32}\{\texttt{176},\texttt{54},\texttt{32}\}; 对于第三个样例,最优(且唯一)的划分是 $\{\texttt 1,\texttt 2,\texttt 3,\texttt 2,\texttt 1\}$。

数据规模与约定

对于 100%100\% 的数据,有 3≤n≤1053\le n\le 10^5,2≤k≤n2\le k\le n。

题目来源

SouthEastern European Regional Contest 2014, Problem B