这题不用快读过不去啊
查看原帖
这题不用快读过不去啊
156042
王半仙楼主2024/3/3 20:50

写了一晚上,各种优化,发现不用快读就是过不了。除了使用快读,不知道该怎么优化了,大神帮看看吧。

#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;
} 
2024/3/3 20:50
加载中...