ZJ c223: Add All(變異版)

題目鏈接:https://zerojudge.tw/ShowProblem?problemid=c223

這題原意是要觀察出合併後數字會遞增

可以用一個queue去存

合併時可以\(O(1)\)取得最小值

全部合併時間複雜度為\(O(n)\)

但這題根本不是考你上面說的那些= =

他需要加一大堆輸入輸出優化

還有RadixSort才能過(據說)

因為我沒刻RadixSort所以只拿到99%

以下為code

#include<bits/stdc++.h>

#include<bits/extc++.h>

using namespace std;

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

long long readint(){

long long a=0;

char c='0';

while(c>='0'&&c<='9'){

a=(a<<3)+(a<<1)+c-'0';

c=getchar();

}

return a;

}

void writeint(long long d){

if(d==0){

putchar(48);

return;

}

int len=0;

char n[20];

while(d>0){

n[len]=d%10+48;

len++;

d/=10;

}

for(int i=len-1;i>=0;i--) putchar(n[i]);

}

int main()

{

//AC

ll n,t,sum;

while(1)

{

n=readint();

if(!n) break;

ll r=0;

queue<ll> pq,q;

vector<ll> v;

while(n--)

{

t=readint();

v.emplace_back(t);

}

sort(v.begin(),v.end());

for(int i=0;i<v.size();i++)

pq.emplace(v[i]);

while(pq.size()+q.size()>1)

{

if(q.size()&&!pq.size()) sum=q.front(),q.pop();

else if(q.size()&&pq.size()&&pq.front()>q.front()) sum=q.front(),q.pop();

else sum=pq.front(),pq.pop();

if(q.size()&&!pq.size()) sum+=q.front(),q.pop();

else if(q.size()&&pq.size()&&pq.front()>q.front()) sum+=q.front(),q.pop();

else sum+=pq.front(),pq.pop();

r+=sum;

q.emplace(sum);

}

cout<<r<<'\n';

}

}