TIOJ 1613 尋找蘿莉

http://tioj.infor.org/problems/1613

結果反而在pE先解出來之前先搞出pF了
因為要讓機率高的試的次數盡量少 所以其實是一顆霍夫曼
結果發現真的建樹的話會MLE
不過反正因為沒有要最後的編碼 只要機率*層數就好
所以就算就好(?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include<bits/stdc++.h> using namespace std; #define ll long long inline int rit(){ int t=0,k=1; char c; do{ c=getchar(); if(c=='-')k=-1; }while(c<'0'||c>'9'); do{ t=t*10+c-'0'; c=getchar(); }while(c>='0'&&c<='9'); return t*k; }; ll n,t,t1,t2; ll ans; priority_queue<ll,vector<ll>, greater<ll> > pq; int main(){ n=rit(); for(int i=0;i<n;i++){ t=rit(); pq.push(t); } while(pq.size()>1){ t1=pq.top();pq.pop(); t2=pq.top();pq.pop(); pq.push(t1+t2); ans+=t1+t2; } cout<<ans<<endl; }