淘宝网站的建设与运营设计思路,居然之家装修公司官网,收费网站怎么建立,长沙网站seo荷马史诗 题目描述 追逐影子的人#xff0c;自己就是影子。 ——荷马 Allison 最近迷上了文学。她喜欢在一个慵懒的午后#xff0c;细细地品上一杯卡布奇诺#xff0c;静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是… 荷马史诗 题目描述 追逐影子的人自己就是影子。 ——荷马 Allison 最近迷上了文学。她喜欢在一个慵懒的午后细细地品上一杯卡布奇诺静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了Allison 想通过一种编码方式使得它变得短一些。 一部《荷马史诗》中有 nnn 种不同的单词从 111 到 nnn 进行编号。其中第 iii 种单词出现的总次数为 wiw_iwi。Allison 想要用 kkk 进制串 sis_isi 来替换第 iii 种单词使得其满足如下要求 对于任意的 1≤i,j≤n, i≠j1 \leq i,j \leq n, \ i \neq j1≤i,j≤n, ij都有sis_isi 不是 sjs_jsj 的前缀。 现在 Allison 想要知道如何选择 sis_isi才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下Allison 还想知道最长的 sis_isi 的最短长度是多少 一些定义 一个字符串被称为 kkk 进制字符串当且仅当它的每个字符是 000 到 k−1k−1k−1 之间包括 000 和 k−1k−1k−1的整数。 字符串 Str1\text{Str}_1Str1 被称为字符串 Str2\text{Str}_2Str2 的前缀当且仅当存在 1≤t≤m1 \leq t \leq m1≤t≤m使得 Str1Str2[1…t]\text{Str}_1\text{Str}_2[1 \ldots t]Str1Str2[1…t]。其中mmm 是字符串 Str2\text{Str}_2Str2 的长度Str2[1…t]\text{Str}_2[1 \ldots t]Str2[1…t] 表示 Str2\text{Str}_2Str2 的前 ttt 个字符组成的字符串。 输入格式 输入文件的第一行包含两个正整数 n,kn,kn,k中间用单个空格隔开表示共有 nnn 种单词需要使用 kkk 进制字符串进行替换。 接下来 nnn 行第 i1i1i1 行包含 111 个非负整数 wiw_iwi表示第 iii 种单词的出现次数。 输出格式 输出文件包括两行。 第一行输出一个整数为《荷马史诗》经过重新编码以后的最短长度。 第二行输出一个整数为保证最短总长度的情况下最长字符串 sis_isi 的最短长度。 输入数据 1 4 2
1
1
2
2Copy 输出数据 1 12
2Copy 输入数据 2 6 3
1
1
3
3
9
9Copy 输出数据 2 36
3Copy 数据范围与提示
限制与约定
Case #nnn 的规模kkk 的规模附加限制1n3n 3n3k2k 2k2-2n5n 5n53n16n 16n16所有 wiw_iwi 均相等4n1000n 1000n1000wiw_iwi 在取值范围内均匀随机5-6n100000n 100000n1000007所有 wiw_iwi 均相等8-9n7n 7n7k3k 3k310n16n 16n16所有 wiw_iwi 均相等11n1001n 1001n100112n99999n 99999n99999k4k 4k413n100000n 100000n100000-1415n1000n 1000n1000k5k 5k516n100000n 100000n100000k7k 7k7wiw_iwi 在取值范围内均匀随机17-18k8k 8k8wiw_iwi 在取值范围内均匀随机19k9k 9k9-20
对于所有数据保证 2≤n≤100000, 2≤k≤9, 0wi≤10112 \leq n \leq 100000, \ 2 \leq k \leq 9, \ 0 \lt w_i \leq 10^{11}2≤n≤100000, 2≤k≤9, 0wi≤1011。选手请注意使用 646464 位整数进行输入输出、存储和计算。
评分方式
对于每个测试点 若输出文件的第 111 行正确得到该测试点 40%40\%40% 的分数 若输出文件完全正确得到该测试点 100%100\%100% 的分数。
#includecstdio
#includecstring
#includequeue
#includealgorithm
#define ll long long
using namespace std;
struct node
{ll w,h;node(){w0,h0;}node(ll w,ll h):w(w),h(h){}bool operator (const node a)const{return a.ww?ha.h:wa.w;}
};
ll ans;
priority_queuenodeq;
int main()
{ll n,k;ans0;scanf(%lld%lld,n,k);for(int i1;in;i){ll w;scanf(%lld,w);q.push(node(w,1));}while((q.size()-1)%(k-1)!0)q.push(node(0,1));while(q.size()k){ll h-1;ll w0;for(int i1;ik;i){node tq.top();q.pop();hmax(h,t.h);wt.w;}answ;q.push(node(w,h1));}printf(%lld\n%lld\n,ans,q.top().h-1);return 0;
}
