做國際貿(mào)易都用什么網(wǎng)站seo優(yōu)化排名是什么
荷馬史詩
題目描述
追逐影子的人，自己就是影子。 ——荷馬
Allison 最近迷上了文學。她喜歡在一個慵懶的午后，細細地品上一杯卡布奇諾，靜靜地閱讀她愛不釋手的《荷馬史詩》。但是由《奧德賽》和《伊利亞特》組成的鴻篇巨制《荷馬史詩》實在是太長了，Allison 想通過一種編碼方式使得它變得短一些。
一部《荷馬史詩》中有 nnn 種不同的單詞，從 111 到 nnn 進行編號。其中第 iii 種單詞出現(xiàn)的總次數(shù)為 wiw_iwi?。Allison 想要用 kkk 進制串 sis_isi? 來替換第 iii 種單詞，使得其滿足如下要求： 對于任意的 1≤i,j≤n,?i≠j1 \leq i,j \leq n, \ i \neq j1≤i,j≤n,?i=j，都有：sis_isi? 不是 sjs_jsj? 的前綴。
現(xiàn)在 Allison 想要知道，如何選擇 sis_isi?，才能使替換以后得到的新的《荷馬史詩》長度最小。在確?？傞L度最小的情況下，Allison 還想知道最長的 sis_isi? 的最短長度是多少？
一些定義：
一個字符串被稱為 kkk 進制字符串，當且僅當它的每個字符是 000 到 k?1k?1k?1 之間（包括 000 和 k?1k?1k?1）的整數(shù)。
字符串 Str1\text{Str}_1Str1? 被稱為字符串 Str2\text{Str}_2Str2? 的前綴，當且僅當：存在 1≤t≤m1 \leq t \leq m1≤t≤m，使得 Str1=Str2[1…t]\text{Str}_1=\text{Str}_2[1 \ldots t]Str1?=Str2?[1…t]。其中，mmm 是字符串 Str2\text{Str}_2Str2? 的長度，Str2[1…t]\text{Str}_2[1 \ldots t]Str2?[1…t] 表示 Str2\text{Str}_2Str2? 的前 ttt 個字符組成的字符串。
輸入格式
輸入文件的第一行包含兩個正整數(shù) n,kn,kn,k，中間用單個空格隔開，表示共有 nnn 種單詞，需要使用 kkk 進制字符串進行替換。
接下來 nnn 行，第 i+1i+1i+1 行包含 111 個非負整數(shù) wiw_iwi?，表示第 iii 種單詞的出現(xiàn)次數(shù)。
輸出格式
輸出文件包括兩行。
第一行輸出一個整數(shù)，為《荷馬史詩》經(jīng)過重新編碼以后的最短長度。
第二行輸出一個整數(shù)，為保證最短總長度的情況下，最長字符串 sis_isi? 的最短長度。
數(shù)據(jù)范圍與提示
限制與約定
| Case # | nnn 的規(guī)模 | kkk 的規(guī)模 | 附加限制 |
|---|---|---|---|
| 1 | n=3n = 3n=3 | k=2k = 2k=2 | - |
| 2 | n=5n = 5n=5 | ||
| 3 | n=16n = 16n=16 | 所有 wiw_iwi? 均相等 | |
| 4 | n=1000n = 1000n=1000 | wiw_iwi? 在取值范圍內(nèi)均勻隨機 | |
| 5 | - | ||
| 6 | n=100000n = 100000n=100000 | ||
| 7 | 所有 wiw_iwi? 均相等 | ||
| 8 | - | ||
| 9 | n=7n = 7n=7 | k=3k = 3k=3 | |
| 10 | n=16n = 16n=16 | 所有 wiw_iwi? 均相等 | |
| 11 | n=1001n = 1001n=1001 | ||
| 12 | n=99999n = 99999n=99999 | k=4k = 4k=4 | |
| 13 | n=100000n = 100000n=100000 | - | |
| 14 | |||
| 15 | n=1000n = 1000n=1000 | k=5k = 5k=5 | |
| 16 | n=100000n = 100000n=100000 | k=7k = 7k=7 | wiw_iwi? 在取值范圍內(nèi)均勻隨機 |
| 17 | - | ||
| 18 | k=8k = 8k=8 | wiw_iwi? 在取值范圍內(nèi)均勻隨機 | |
| 19 | k=9k = 9k=9 | - | |
| 20 |
對于所有數(shù)據(jù)，保證 2≤n≤100000,?2≤k≤9,?0<wi≤10112 \leq n \leq 100000, \ 2 \leq k \leq 9, \ 0 \lt w_i \leq 10^{11}2≤n≤100000,?2≤k≤9,?0<wi?≤1011。選手請注意使用 646464 位整數(shù)進行輸入輸出、存儲和計算。
評分方式
對于每個測試點：
若輸出文件的第 111 行正確，得到該測試點 40%40\%40% 的分數(shù)；
若輸出文件完全正確，得到該測試點 100%100\%100% 的分數(shù)。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;
struct node
{ll w,h;node(){w=0,h=0;}node(ll w,ll h):w(w),h(h){}bool operator <(const node &a)const{return a.w==w?h>a.h:w>a.w;}
};
ll ans;
priority_queue<node>q;
int main()
{ll n,k;ans=0;scanf("%lld%lld",&n,&k);for(int i=1;i<=n;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 w=0;for(int i=1;i<=k;++i){node t=q.top();q.pop();h=max(h,t.h);w+=t.w;}ans+=w;q.push(node(w,h+1));}printf("%lld\n%lld\n",ans,q.top().h-1);return 0;
}