问题
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 位整数。
代码
/* 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("%lld ",solve()); } return 0; }