NC17884. [NOI2015]荷马史诗
描述
现在 Allison 想要知道，如何选择 si，才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下，Allison 还想知道最长的 si 的最短长度是多少？
一个字符串被称为 k 进制字符串，当且仅当它的每个字符是 0 到 k−1 之间（包括 0 和 k−1）的整数。
字符串 Str1 被称为字符串 Str2 的前缀，当且仅当：存在 1≤t≤m，使得 Str1=Str2[1..t]。其中，m 是字符串 Str2 的长度，Str2[1..t] 表示 Str2 的前 t 个字符组成的字符串。
输入描述
第 1 行包含 2 个正整数 n,k，中间用单个空格隔开，表示共有 n 种单词，需要使用 k 进制字符串进行替换。
接下来 n 行，第 i+1 行包含 1 个非负整数 wi，表示第 i 种单词的出现次数。
输出描述
包括 2 行。
第 1 行输出 1 个整数，为《荷马史诗》经过重新编码以后的最短长度。
第 2 行输出 1 个整数，为保证最短总长度的情况下，最长字符串 si 的最短长度。
示例1
输入:
4 2 1 1 2 2
输出:
12 2
说明:
用 X(k) 表示 X 是以 k 进制表示的字符串。C++14(g++5.4) 解法, 执行用时: 78ms, 内存消耗: 3676K, 提交时间: 2020-03-25 07:28:32
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PLL;
ll n,k;
int main()
{
cin>>n>>k;
priority_queue<PLL,vector<PLL>,greater<PLL>> q;
for(int i=0;i<n;i++){
ll x;
cin>>x;
q.push({x,0});
}
while((q.size()-1)%(k-1)!=0) q.push({0,0});
ll ans=0;
while(q.size()>1){
ll deep=-1,sum=0;
for(int i=0;i<k;i++){
auto x=q.top();q.pop();
deep=max(deep,x.second);
sum+=x.first;
}
ans+=sum;
q.push({sum,deep+1});
}
cout<<ans<<endl;
cout<<q.top().second<<endl;
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 48ms, 内存消耗: 2620K, 提交时间: 2023-07-28 21:21:33
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,w,ans1=0,ans2=0,res=0,k;priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,greater<pair<long long,long long> > >q;scanf("%lld%lld",&n,&k);
for(register int i=1;i<=n;++i)scanf("%lld",&w),q.push({w,0});
while((n-1)%(k-1)!=0)q.push({0,0}),++n;
while(q.size()>1){
res=0;ans2=-1e18;
for(register int i=1;i<=k;++i)res+=q.top().first,ans2=max(ans2,q.top().second),q.pop();
q.push({res,ans2+1}),ans1+=res;
}
printf("%lld\n%lld",ans1,q.top().second);
}
C++(clang++ 11.0.1) 解法, 执行用时: 83ms, 内存消耗: 2592K, 提交时间: 2022-10-23 15:10:18
#include<bits/stdc++.h>
#define PLI pair<ll,int>
#define ll long long
using namespace std;
priority_queue<PLI,vector<PLI>,greater<PLI>>hf;
int n,k;int main(){
cin>>n>>k;
for(int i=0;i<n;i++){
ll x;cin>>x;
hf.push({x,0});
}
while((n-1)%(k-1))hf.push({0,0}),n++;
ll sum=0;while(hf.size()>1){
ll s=0;int dp=0;
for(int i=0;i<k;i++){
auto t=hf.top();
s+=t.first,dp=max(dp,t.second),hf.pop();
}sum+=s,hf.push({s,dp+1});
}cout<<sum<<endl<<hf.top().second<<endl;
}