问题
Fate 有 n 个 ACM/ICPC 比赛的模板，每个都是一个独立的 PDF 文件。为了便于打印，万神希望将这些模板合并成一个 PDF 文件。万神有一个工具，可以将至多 k 个 PDF 文件合并为 1 个，合并后的文件大小是原来 k 个文件的大小之和。万神发现，这个工具每次运行的时间正比于输出文件的大小。设每输出 1KB 需要 1 单位时间，那么万神至少要多少时间才能合并完所有的文件呢？
输入格式
输入文件包含多组数据（最多 100 组），请处理到文件结束。 每组数据包含 2 行，第 1 行包含两个整数 n、k，用空格分割。 第二行包含 n 个整数 s1 · · · sn，用空格分割，表示原始的 n 个模板文件的大小（单位为 KB）。 保证 1 ≤ n ≤ 1000，2 ≤ k ≤ 1000，1 ≤ si ≤ 109。
输出格式
对于每组数据输出 1 行，表示合并所有文件需要的最短时间。
输入样例
7 4 1 2 3 4 5 6 7 3 5 1 2 3
输出样例
38 6
样例解释
对于第一组样例，首先合并前 4 个文件，耗费 10 单位时间。之后把生成的大小 10KB 的文件和后 3 个文件合并，耗费 28 单位时间，共计 38 单位时间。不存在时间更少的合并方案。 对于第二组样例，可以一次合并所有文件。
HINT
对于较大的数据，你可能需要使用 64 位整数。
代码
代码语言：javascript复制/*
problem:合并模板
task: 一次最多合并k个pdf花费代价为合并页数之和，求合并n个页数为si的pdf的最小代价。
tutorial: 对于每页，参与合并的次数越多，总代价越大，所以每次尽量合并k个最少页数的。
注意到如果每次合并k个后最后一次只需合并少于k个，那么，让第一次合并少于k个，这样可以花费更少代价将其合并为1个pdf。
可以每次都排一次序，不过维护两个单调队列也可以，只要排一次序。
s是未合并的，h是合并过的。
每次取min(min(s),min(h)),min(s)就是s.top，min(h)就是h.top。
合并好的插入h队列。每次合并时累加答案。
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1005
#define ll long long
using namespace std;
int n,k,t,p;
ll s[N],h[N];
ll solve()
{
int top=p 1,htop=0;
printf("p=%d %d",p,h[0]);
ll ans=p?h[0]:0;//加上第一次合并的代价，p==0即没有合并过，则h[0]==s[0]，ans要=0，而不是h[0]。
for(int i=1; i<=t; i )//合并t次
{
for(int j=0; j<k; j )//合并k个
if(htop==i||s[top]<h[htop]&&top<n)//第i次合并如果前面i-1次合并的已经用过了，就不能再从h里面选了
h[i] =s[top ];
else
h[i] =h[htop ];
ans =h[i];//累加答案
}
return ans;
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
memset(h,0,sizeof h);
for(int i=0; i<n; i )
scanf("%lld",&s[i]);
sort(s,s n);
t=(n-1)/(k-1);//每次最大合并减少k-1个pdf，全部合并需要减少n-1张，于是需要t次最大合并（t是向下取整的）
p=n-1-t*(k-1);//还要一次合并是减少p（p<k-1）张的。
for(int i=0; i<=p; i )//合并最小的p 1张
h[0] =s[i];
printf("%lldn",solve());
}
return 0;
}
