【NOI2015】荷马史诗

追逐影子的人，自己就是影子。 ——荷马

Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。

一部《荷马史诗》中有

对于任意的

现在 Allison 想要知道，如何选择

一个字符串被称为

字符串

输入格式

输入文件的第

接下来

输出格式

输出文件包括 2 行。

第

样例一

input

output

12
2

explanation

用

一种最优方案：令

最长字符串

一种非最优方案：令

最长字符串

样例二

input

output

36
3

explanation

一种最优方案：令

样例三

见样例数据下载。

限制与约定

测试点编号			备注	约定
1
2
3			所有
4
5
6
7			所有
8
9
10			所有
11			所有
12			所有
13
14
15
16
17
18
19
20

对于所有数据，保证

选手请注意使用 64 位整数进行输入输出、存储和计算。

时间限制：

空间限制：

评分方式

对于每个测试点：

若输出文件的第

若输出文件完全正确，得到该测试点 100% 的分数。

时间回到NOIday2:额k=2是哈夫曼树，那k大一点是不是就是k叉哈夫曼树呢？于是写了这个程序：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<queue>
#define rep(s,t) for(int i=s;i<=t;i++)
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int maxn=100010;
ll A[maxn];
int n,k;
struct Arr {
    ll v;int cur;
    bool operator < (const Arr& ths) const {
        if(v!=ths.v) return v>ths.v;
        return cur>ths.cur;
    }
};
priority_queue<Arr> Q;
int main() {
    n=read(),k=read();
    rep(1,n) A[i]=read();
    ll ans=0;
    rep(1,n) Q.push((Arr){A[i],0});
    while(Q.size()!=1) {
        ll sum=0;int mx=0;
        for(int j=0;j<k;j++) {
            if(Q.size()) sum+=Q.top().v,mx=max(mx,Q.top().cur),Q.pop();
            else break;
        }
        ans+=sum;Q.push((Arr){sum,mx+1});
    }
    printf("%lld
%d
",ans,Q.top().cur);
    return 0;
}

View Code

发现过不了样例二，我就说肯定不可能这么简单么，于是开始想一些奇怪的DP之类的东西，1h过去后弃疗，手算了第10、11、12三个点走人，得分60。

后来听了ZSY巨神的教导，发现我的程序加上一行就可以AC了233

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<queue>
#define rep(s,t) for(int i=s;i<=t;i++)
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int maxn=100010;
ll A[maxn];
int n,k;
struct Arr {
    ll v;int cur;
    bool operator < (const Arr& ths) const {
        if(v!=ths.v) return v>ths.v;
        return cur>ths.cur;
    }
};
priority_queue<Arr> Q;
int main() {
    n=read(),k=read();
    rep(1,n) A[i]=read();
    while((n-1)%(k-1)) n++;
    ll ans=0;
    rep(1,n) Q.push((Arr){A[i],0});
    while(Q.size()!=1) {
        ll sum=0;int mx=0;
        for(int j=0;j<k;j++) {
            if(Q.size()) sum+=Q.top().v,mx=max(mx,Q.top().cur),Q.pop();
            else break;
        }
        ans+=sum;Q.push((Arr){sum,mx+1});
    }
    printf("%lld
%d
",ans,Q.top().cur);
    return 0;
}

View Code

“注意每次合并k个的话最后一次可能不到k个，那么把最后一次挪到最开始合并，答案最优”。

好，Au无望了