【XDU1144】合并模板

问题

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+,htop=;

    printf("p=%d %d",p,h[]);

    ll ans=p?h[]:;//加上第一次合并的代价，p==0即没有合并过，则h[0]==s[0]，ans要=0，而不是h[0]。

    for(int i=; i<=t; i++)//合并t次

    {

        for(int j=; 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,,sizeof h);

        for(int i=; i<n; i++)

            scanf("%lld",&s[i]);

        sort(s,s+n);

        t=(n-)/(k-);//每次最大合并减少k-1个pdf，全部合并需要减少n-1张，于是需要t次最大合并（t是向下取整的）

        p=n--t*(k-);//还要一次合并是减少p（p<k-1）张的。

        for(int i=; i<=p; i++)//合并最小的p+1张

            h[]+=s[i];

        printf("%lld\n",solve());

    }

    return ;

}

巴特西