C++解析codeforces 1806C

这是一道比较基础的数学题。

首先，我们可以将 $n$ 个数的和表示为 $S = a_1 + a_2 + \cdots + a_n$。

我们可以用 $k$ 表示要将这 $n$ 个数分成的部分数，那么每一部分的和为 $S/k$。

接下来我们需要证明，当 $a_1,a_2,\cdots,a_n$ 中存在一个数 $a_i$，使得它大于 $S/k$ 时，无论如何分割都不可能使得每一部分的和都小于等于 $S/k$。

我们可以假设将 $a_i$ 分到了某一部分中，那么这一部分的和就是 $S_i \geq S/k + a_i > S/k$，剩下的 $n-1$ 个数的和为 $S-S_i$。

如果我们将这 $n-1$ 个数分成 $k-1$ 部分，那么每一部分的和为 $(S-S_i)/(k-1)$。

因为 $S_i > S/k$，所以 $(S-S_i)/(k-1) < S/k$，即这 $n-1$ 个数无论如何分割都可以使得每一部分的和都小于等于 $S/k$。

所以，为了使得每一部分的和都小于等于 $S/k$，我们需要将所有大于 $S/k$ 的数都分到不同的部分中。

那么，我们可以先将原数组从大到小排序，然后依次将每一个大于 $S/k$ 的数分到不同的部分中，如果已经分到了 $k$ 个部分，则将剩下的大于 $S/k$ 的数全部舍弃。

最后，我们统计一下每一部分的和即可。时间复杂度为 $O(n\log n)$。