10082. 「一本通 3.3 例 1」Word Rings

题意

每组数据读入一个n和n个字符串。定义前2个与末尾2个字母相同可以连接。问使这个环串的平均长度最大。求这个最大值。不存在输出No solution。

思路

平均值公式:
$$Average=(E_1+E_2+…..+E_n)/n$$ $$Average*n=(E_1+E_2+…+E_n)$$ $$(E_1-Average)+(E_2-Average)+…+(E_n-Average)=0$$ 那么可以二分答案:
$$(E_1-Ans)+(E_2-Ans)+…+(E_n-Ans)\geq0$$
然后瞎搞spfa。
暂无评论

发送评论


				
上一篇
下一篇