题外话:
下面机房 + 红名大佬 changwenxuan 已经写得很详细了,但是我觉得有些部分讲的比较粗糙,所以写了这篇题解。
原题链接
题目解析:
- 「insert \(x\)」 操作:直接将 \(x\) 加入小根堆。
- 「getMin \(x\)」 操作:表示在完整的堆操作里,堆中最小值为 x,注意!是完整的堆操作。
- 「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 ++ ;
}
}
最后的代码没啥难度了,就不给了。