写了一晚上,各种优化,发现不用快读就是过不了。除了使用快读,不知道该怎么优化了,大神帮看看吧。
#include <cstdio>
#include <queue>
using namespace std;
struct Node{
long long value;
int num;
}a[2];
queue<Node> q2;
int n,t,k,book[100005];
long long ans;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&t);
++book[t];
}
for(int i=1;i<=100000;++i){
if(book[i] != 0){
a[k].value = i;
a[k].num = book[i];
if(a[k^1].num == 1){
t = a[k].value + a[k^1].value;
ans += t;
if(t<=100000) ++book[t];
else q2.push(Node{t,1});
--a[k].num;
}
if(a[k].num > 1){
t = a[k].value<<1;
ans += t * (a[k].num>>1);
if(t<=100000) book[t] += a[k].num>>1;
else q2.push(Node{t,a[k].num>>1});
a[k].num &= 1;
}
k ^= 1;
}
}
while(!q2.empty()){
a[k] = q2.front();
q2.pop();
if(a[k^1].num == 1){
ans += a[k].value + a[k^1].value;
q2.push(Node{a[k].value + a[k^1].value,1});
--a[k].num;
}
if(a[k].num > 1){
ans += a[k].value*(a[k].num & -2);
q2.push(Node{a[k].value<<1,a[k].num>>1});
a[k].num &= 1;
}
k ^= 1;
}
printf("%lld",ans);
return 0;
}