CF226B Naughty Stone Piles

桌上有 $n$ 堆石子，数量分别为 $a_{1},a_{2},...,a_{n}$。 每次操作，你可以选择一堆石子，将其加入到另一堆中。将第 $i$ 堆石子加入第 $j$ 堆时，第 $j$ 堆石子的数量增加当前第 $i$ 堆的石子数，第 $i$ 堆则不再存在。此次操作的代价等于被加入的那堆（即第 $i$ 堆）的石子数。 你的任务是，计算把所有石子合并成一堆所需的最小总代价。 为了增加难度，这些石子堆联合起来设立了限制：每一堆被加入其他堆的次数最多不超过 $k$ 次（达到 $k$ 次后，这堆只能被加入到别的堆，不能再作为目标被别的堆合并了）。 更进一步，石子堆给出了 $q$ 个（不一定不同的）$k$ 的取值。 你的任务是，对于每个 $k$ 的取值，输出其对应的最小合并总代价。

第一行包含一个整数 $n$ $(1 \leq n \leq 10^{5})$，表示石子堆的数量。第二行包含 $n$ 个空格分隔的整数 $a_{1},a_{2},...,a_{n}$ $(1 \leq a_{i} \leq 10^{9})$，表示每堆石子的初始数量。 第三行包含一个整数 $q$ $(1 \leq q \leq 10^{5})$，表示询问的数量。最后一行包含 $q$ 个空格分隔的整数 $k_{1},k_{2},...,k_{q}$ $(1 \leq k_{i} \leq 10^{5})$，表示每次询问的 $k$ 值，$k$ 的取值可以重复。

输出 $q$ 个用空格分隔的整数，依次对应每一个查询的答案。 请注意，在 C++ 中读取和输出 64 位整数时，不要使用 %lld；建议使用 cin、cout 流或 %I64d。

在第一个样例中，一种取得最优答案的方法如下：依次将第 $4$、$5$ 堆石子合并到第 $2$ 堆上；然后把第 $1$ 堆合并到第 $3$ 堆；最后把第 $2$ 堆再合并到第 $3$ 堆。前两步操作都各花费 $1$，第三步花费 $2$，第四步花费 $5$（注意合并前第 $2$ 堆的数量已经变成 $5$ 了，不是 $3$）。 在第二个样例中，你可以先将第 $2$ 堆合并到第 $3$ 堆（花费 $3$），再将第 $1$ 堆合并到第 $3$ 堆（花费 $2$），将第 $5$ 堆合并到第 $4$ 堆（花费 $1$），最后将第 $4$ 堆合并到第 $3$ 堆（花费 $2$）。 由 ChatGPT 5 翻译