CF681C-Heap Operations

发布时间 2023-12-27 09:46:59作者: emo_male_god

题外话:

下面机房 + 红名大佬 changwenxuan 已经写得很详细了,但是我觉得有些部分讲的比较粗糙,所以写了这篇题解。


原题链接

题目解析:

  1. 「insert \(x\)」 操作:直接将 \(x\) 加入小根堆。
  2. 「getMin \(x\)」 操作:表示在完整的堆操作里,堆中最小值为 x,注意!是完整的堆操作。
  3. 「removeMin」 操作:pop 掉堆中最小的值,这里埋个小小的伏笔

先给思路:我们维护一个小根堆,题目给什么操作我们就做什么操作。但是如果操作不合法,我们就要分类讨论

不合法操作1:

当前小根堆的最小值为 \(x\),但是题目 getMin 函数返回的却比 \(x\) 更小。

解决方法:在堆不为空的情况下,把比 \(x\) 更大的数都 pop 掉,再 push 进 \(x\)


不合法操作2:

当前堆已经空了,但题目给了 getMin \(x\) 函数。

解决方法:直接push \(x\) 再 getMin \(x\)


不合法操作3:

当前堆已经空了,但题目给了 removeMin 函数。

解决方法:注意!这里要先随便 push 进一个合法的数,再 removeMin。(我就是在这里改了好几个小时[大哭])


注释:以下代码中的 s 为题目给的函数,o 为函数中的值,ans 为存储输出的结构体数组,q 为小根堆,cnt 为最后输出操作的个数。(其实不用计数,直接输出数组的长度也可以)


insert 部分代码:

if (s == "insert")
{
	cin >> o;
	q.push(o);
	ans.push_back({s, o});
	cnt ++ ;
}

removeMin 部分代码:

if (s == "removeMin")
{
	if (q.empty())//如果堆为空,要先随便insert一个数,再删除
	{
		ans.push_back({"insert", 114514});
		cnt ++ ;
		
		ans.push_back({s});
		cnt ++ ;
	}
	else//如果不为空,直接删除
	{
		q.pop();
		ans.push_back({s});
		cnt ++ ;
	}
}


getMin 部分代码:

if (s == "getMin")
{
	cin >> o;
	if (q.empty())//如果堆为空,先insert再getMin
	{
		ans.push_back({"insert", o});
		q.push(o);
		cnt ++ ;
		ans.push_back({"getMin", o});
		cnt ++ ;
	}
	else//如果堆不为空,就继续判断
	{
		if (q.top() < o)//如果堆中有比o更小的数,就全部pop掉
		{
			while (!q.empty() && q.top() < o)//pop
			{
				q.pop();
				ans.push_back({"removeMin", q.top()});
				cnt ++ ;
			}
			if (q.empty())//如果pop完堆空了,直接insert
			{
				q.push(o);
				ans.push_back({"insert", o});
				cnt ++ ;
			}
			else if (q.top() != o)//如果还有数且不等于要查询的数,insert
			{
				q.push(o);
				ans.push_back({"insert", o});
				cnt ++ ;
			}
		}
		else if (q.top() != o)//如果堆中没有比o更小或等于的数,insert
		{
			q.push(o);
			ans.push_back({"insert", o});
			cnt ++ ;
		}
		ans.push_back({"getMin", o});//往答案数组里面加
		cnt ++ ;
	}
}

最后的代码没啥难度了,就不给了。