样例过了,大量WA,求调
查看原帖
样例过了,大量WA,求调
940854
Jianbing_Juan楼主2023/11/6 00:02

有代码和出错测试点数据。

我总是看不出我的代码逻辑错误在哪。已经逐行检查过了。不知道为什么和预期结果不同

record

problem P3378

code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// data structure: heap

inline int _ls(int x)
{
	return 2*x+1;
}
inline int _rs(int x)
{
	return 2*x+2;
}
inline int _fa(int x)
{
	return (x-1)/2;
}
class _heap // 小根堆 
{
	private:
		vector<int> Heap;
	public:
		int size=0;
		void push(int x)
		{
			Heap.push_back(x);
			int p=size;
			size++;
			if(!p)
			return;
			while(Heap[_fa(p)]>Heap[p] and p>0)
			{
				swap(Heap[_fa(p)],Heap[p]);
				p=_fa(p);
			}
		}
		int top(void)
		{
			if(!size)
			return 0;
			return Heap[0];
			
		}
		void pop(void)
		{
			if(!size)return;
			size--;
            
			swap(Heap[size],Heap[0]);
			int p=0,minp;
			while(_ls(p)<size)
			{
                minp=(Heap[_ls(p)]<Heap[_rs(p)])?_ls(p):_rs(p);
                if(_rs(p)==size)
                minp=_ls(p);
                if(Heap[p]>Heap[minp])
				swap(Heap[p],Heap[minp]);
                else
                break;
				p=minp;
			}
		}
};


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	_heap a;
	int n,op,x;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>op;
		if(op==1)
		{
			cin>>x;
			a.push(x);
		}
		else if(op==2)
		{
			cout<<a.top()<<endl;
		}
		else
		{
			a.pop();
		}
	}
}

data

input

15
1 5384
2
3
1 4337
1 291
3
1 3776
2
1 2490
1 3903
1 5038
1 4504
3
3
3
  
output

5384
3776

2023/11/6 00:02
加载中...