luogu#P2112. 鸿雁传书

鸿雁传书

题目背景

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

题目描述

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

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

输入格式

11 行,两个正整数 N,KN,K

22 行,NN 个空格隔开的单词。

输出格式

一行,一个 11 位小数表示每行字母数的最小方差。

4 2
xxx xxxxx xxxx xx
(输入的本来是一封情书,被和谐了……)
1.0

提示

【样例说明】

xxx xxxxx
xxxx xx

1÷2×((87)2+(67)2)=11 \div 2 \times ((8-7)^2+(6-7)^2) = 1

【数据范围】

对于 30%30\% 数据,N100N \leq 100K3K \leq 3

对于全部数据,N1000N \leq 1000K100K \leq 100,单词长度 20\leq 20