求助
查看原帖
求助
727723
ypyxc楼主2022/6/21 11:57

自己编译器运行对 提交时是这样的 Runtime Error. Received signal 11: Segmentation fault with invalid memory reference.

就是自己简单写了个堆

#include<iostream>
using namespace std;


int cnt;

class my_heap
{
public:
	int *arr;
	int cursize;
	int maxsize;
	my_heap()
	{
		maxsize = 10005;
		arr = new int[maxsize];
	}
	int get_first()
	{
		return arr[0];
	}

	void siftUp(int p)
	{
		int temp = arr[p];
		int ppa = (p - 1) / 2;


		if (ppa < 0)return;

		if (temp < arr[ppa])
		{
			arr[p] = arr[ppa];
			arr[ppa] = temp;
			siftUp(ppa);
		}
		else return;
	}


	void intsert(int a)
	{
		arr[cursize] = a;
		siftUp(cursize);
		cursize++;
	}


	void siftDown(int p)//找小的放到上面
	{
		int temp = arr[p];
		while (p*2+1 <= cursize - 1)
		{
			int cur = p * 2 + 1;
			if (p * 2 + 2 <= cursize - 1 && arr[p * 2 + 1]>arr[p * 2 + 2]) cur =cur+1;
			if (temp <=arr[cur])break;
			arr[p] = arr[cur];
			p = cur;
		}
		arr[p] = temp;
	}

	void pop()
	{
		arr[0] = arr[cursize - 1];
		cursize--;
		siftDown(0);
	}
};
int main()
{

	my_heap hp;

	cnt= 0;
	int n;
	cin >> n;
	while (n--)
	{
		int a;
		cin >> a;
		hp.intsert(a);
	}


	while (hp.cursize > 1)
	{
		int a = hp.get_first();
		hp.pop();
		cnt+= a;
		int b = hp.get_first();
		hp.pop();
		cnt += b;
		hp.intsert(a + b);
	}
	cout<<cnt;
	return 0;
}
2022/6/21 11:57
加载中...