10分超时,一个有关set的求教
查看原帖
10分超时,一个有关set的求教
255762
lyxleo楼主2022/11/2 23:32

我原来用优先队列写了一个版本,这次回来改用set做,但是发现set超时,自己写了个数据生成器,共2000个果子,枚举到七百多的时候,set自己出了问题,导致超时,我用gdb调试,调不出来哪里错了。

我估计是我查询堆最小值那部分的代码错了,谁能看看为啥错了?

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
using namespace std;
int n;
set <int> min_heap;
int ans;
int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;++i){
		int x;
		scanf("%d",&x);
		min_heap.insert(x);
	}
	for(int i = 1;i < n;++i){
		int x = *min_heap.begin();
		min_heap.erase(min_heap.begin());
		int y = *min_heap.begin();
		min_heap.erase(min_heap.begin());
		ans += x + y;
		min_heap.insert(x + y);
	}
	printf("%d",ans);
	return 0;
}
2022/11/2 23:32
加载中...