OneDay的小球

发布时间: 2018年1月29日 10:26   最后更新: 2018年2月11日 23:54   时间限制: 2000ms   内存限制: 128M

OneDay有$n$个不同的盒子,起初在第一个盒子中有$n$种不同颜色的小球。

OneDay有些无聊,想搞点幺蛾子。他想要把这些小球分别放到对应的盒子中,即第$i$个盒子中$(1≤i≤n)$存放所有颜色为$i$的小球。为了做到这一点,OneDay可以进行以下操作:

  1. 选择任意一个非空的盒子,拿出盒子里所有的小球;
  2. 选择$k$个空盒子(第$1$步中选择的盒子变成了空盒子,此处也可选)将上一步取出的球分成$k$个非空集合,分别放入这$k$个盒子中。他只能选择$k=2$或$k=3$。

OneDay每一次操作的代价为他每次在第1步中拿出的小球的个数。那么整个过程他所需花费的最小代价是多少?

有多组测试数据,(数据组数$≤20$)。对于每组数据,第一行有两个整数$n$表示盒子和颜色的数量。第二行有$n$个数$a_1,a_2,…,a_n$,表示第$i$种颜色小球的个数,中间以空格分割。

对于每组测试数据,输出一个整数表示OneDay的最小代价。
$1≤n≤2·10^5$
$1≤a_i≤10^9$

复制
3
1 2 3
4
2 3 4 5
6
19

本题的输入数据量较大,建议使用高效的读写方式:C++使用scanf/printf代替cin/cout,Java使用BufferedReader/PrintWriter代替Scanner/System.out。

第一个样例:从第一个盒子中拿出所有的球,选择$k=3$,将三种颜色的球分别放入对应的盒子中。总代价为$6$。

第二个样例需要两步:

  1. 从第一个盒子中拿出所有的球,选择$k=3$,把所有颜色$3$的球放入第三个盒子,颜色$4$的球放入第四个盒子,其余的球放回第一个盒子。代价为$14$;
  2. 从第一个盒子中拿出所有的球,选择$k=2$,把所有颜色$1$的球放入第一个盒子,颜色$2$的球放入第二个盒子。代价为$5$。

总代价为$19$。

basic algorithm

Weekly Training 2018.1.28