分数: 1000 点
问题陈述
给你一个字符串 S 由之间的数字组成 1 和 9,包括在内。
您最多将插入 K 逗号 (,) 插入该字符串以将其分成多个数字。
您的任务是最小化通过插入逗号产生的最大数量。找到该值的最小可能值。
约束
- 0 ≦ K < |S| ≦ 100,000
- S 由之间的数字组成
1和9,包括在内。
部分分数
- 在测试集中值得 100 点, |S| ≦ 2.
- 在测试集中值得另一个 100 点, |S| ≦ 16.
- 在测试集中值得另一个 200 点, |S| ≦ 100.
- 在测试集中值得另一个 200 点, |S| ≦ 2,000.
输入
输入由标准输入按以下格式给出:
K S
输出
打印最小可能值。
示例输入 1
2 15267315
示例输出 1
315
当字符串被分成 152, 67 和 315,其中最大的是 315,这是可能的最小值。
示例输入 2
0 12456174517653111
示例输出 2
12456174517653111
12456174517653111 本身就是答案。
示例输入 3
8 127356176351764127645176543176531763517635176531278461856198765816581726586715987216581
示例输出 3
5317635176