实验报告缝合
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Problem Description
事实上,真实的做法是将学长的实验报告 copy 后,修改名字,没了。
你是一名深陷期末月的大学生。在《算法设计与分析》这门课上,教授要求每人提交一份实验报告。
幸运的是,你从往届学长那里搞到了 $n$ 份现成的报告,第 $i$ 份有 $a_i$ 页,直接交会被查重系统当场逮捕。你的策略是:每次选取至多 $k$ 份报告,把它们摞在一起,封面写上自己的名字——这就“合成”了一份新报告。每次合成的代价为这些报告的总页数。合成后得到一份新报告,其页数为合成前的页数之和。
除了实验报告,你还有很多事情要忙,比如说:谈恋爱、和朋友吃饭、游玩舞萌等等,所以你希望合成最终实验报告的总代价最小,请求出这个总代价。
Input Format
第一行一个整数 $T$($1 \le T \le 1000$),表示测试数据组数。
每组数据:
第一行两个整数 $n, k$($2 \le k \le n \le 2 \times 10^5$)。
第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$($1 \le a_i \le 10^9$),表示每份报告的页数。
保证所有测试数据的 $\sum n \le 2 \times 10^5$。
Output Format
输出 $T$行,每行输出一行一个整数,表示最小总代价。
2
5 3
1 2 3 4 5
4 2
3 5 1 2
21
20
Hint
对于第一组测试用例:
第 $1$ 次,合并 $3$ 份报告,代价分别为$\{1,2,3\}$,代价 $6$,得到一份页数为 $6$ 的报告。
第 $2$ 次,合并 $3$ 份报告,代价分别为 $\{4,5,6\}$,代价 $15$,得到一份页数为 $15$ 的报告。
总代价 $6 + 15 = 21$。
2026江南程序设计竞赛联盟暑期多校训练-第一场(重现)
- Status
- Done
- Rule
- XCPC
- Problem
- 12
- Start at
- 2026-10-17 12:00
- End at
- 2026-10-17 17:00
- Duration
- 5 hour(s)
- Host
- Partic.
- 0