PAT-Advanced-1057. Stack

Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to implement a stack with an extra operation: PeekMedian — return the median value of all the elements in the stack. With N elements, the median value is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th if N is odd.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<= 105). Then N lines follow, each contains a command in one of the following 3 formats:

Push key
Pop
PeekMedian

where key is a positive integer no more than 105.

Output Specification:

For each Push command, insert key into the stack and output nothing. For each Pop or PeekMedian command, print in a line the corresponding returned value. If the command is invalid, print “Invalid” instead.

Sample Input:

Sample Output:

一道很有意思的题,题目的难点在于 PeekMedian 的实现,如果直接去遍历,则一定会超时,而且栈中的数可能一直在变化,采用 BFPRT 取中值在复制数组时会付出更大的时间开销。考虑到,“where key is a positive integer no more than 105”,可以考虑直接开一个数组来记录某个 key 是否存在以获取中值(第 k 个存在的数即为中值,若采用0与1来区分,那么数组元素直接累加至 k 时的下标值即为中值),但是也会超时。这里就用了树状数组以提升累加运算的效率,同时采用二分查找来确定中值。

代码如下:

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注