题目内容

小红是一位喜欢玩数字游戏的小朋友。有一天，他在网上看到了一个有趣的挑战：

给定一个仅包含 $2$ 和 $3$ 的数组，如何重新排列它，使得所有连续子数组的权值之和尽可能小？数组的权值定义为数组所有元素乘积的因子数量。

思路:贪心 + 数学

step1:答案结构

直观显然是$2,...,2,3,...,3$ 这种排列权值和最小。

因为考虑一个固定的区间长度，$d(2^{k}) = k + 1 , d(2^{x} * 3^{k-x}) = (x+1) * (k-x+1) > d(2^{k})$。 所以肯定是让区间内相同数尽量多。