3878 - 鸿雁传书

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 1 秒

内存限制 : 128 MB

小明给小红写了一封情书，他想把文章变得更完美，所以要进行排版。

他一共写了 $N$ 个单词，为了美观，要把 $N$ 个单词分成 $K$ 行。单词的相对顺序不能变化。为了简化问题，无需考虑单词间的空格。

小红会喜欢整齐的情书，小明想赢得小红的芳心，所以，他找到你，想让你帮他写一个程序，帮他排版，使得每行字母数的方差最小。请你求出最小的方差。

第 $1$ 行，两个正整数 $N,K$ 。

第 $2$ 行， $N$ 个空格隔开的单词。

一行，一个 $1$ 位小数表示每行字母数的最小方差。

4 2
xxx xxxxx xxxx xx

1.0

【样例说明】

xxx xxxxx
xxxx xx

$1 \div 2 \times ((8-7)^2+(6-7)^2) = 1$ 。

【数据范围】

对于 $30\%$ 数据， $N \leq 100$ ， $K \leq 3$ 。

对于全部数据， $N \leq 1000$ ， $K \leq 100$ ，单词长度 $\leq 20$ 。

luogu