题目内容

小塔有一个长度为$n$的数组$a$，他定义了一个函数$f:f(l,r)=\sum^r_{k=l}a_k$，即$f$($l,r$)表示数组$a$在[$l,r$]这一段区间的区间和。

现在小塔有一个重新任意排列数组$a$的机会，他想要最小化$\sum^n_{l=1}\sum^n_{r=l}f(l,r)$，即最小化所有区间对于f的值之和，请你帮他算算最小的这个值吧。

思路

题目要求枚举左右端点，求解出所有的区间和，这使得每个位置在区间中的贡献不同。例如，在样例$1$中，所有的子区间为 $[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]$。其中，位置$1$贡献$2$次，位置$2$贡献$4$次，位置$3$贡献$2$次。题目要求最小化子区间和，因此需要让较大的数贡献较少的次数。将较大的数放在贡献次数少的位置，比如将$2$和$3$放在位置$1$和$3$，数字$1$放在贡献次数较多的位置$2$。最终数组排列结果为$[2,1,3]$或$[3,1,2]$，最小值为$19$。

对于每个位置，统计其贡献次数，然后通过排序将数值大的数放置在贡献次数少的位置。对于位置$i$，包含$i$的区间$[l, r]$满足$l \leq i \leq r$，因此有$0 \leq l \leq i, i \leq r < n$。位置$i$的贡献次数$nums[i]$为$(i+1) \times (n-i)$。最小的贡献即为排序后的每个数乘以对应的贡献次数：