关于c++:PAT甲级1057-Stack

题目粗心

现有一个栈，对其进行执行N次基本操作，该操作有三种类型，别离是Pop,Push和PeekMedian，代表了出栈，入栈和获取栈中元素的中位数，要求依照每一次输出的指令进行相应的输入

算法思路

这里最为简单的就是实时的获取栈中的中位数，应用拷贝到数组排序或者set汇合都会超时，这里借助分块的思维来实现实时获取中位数，除了应用栈st来进行入栈和出栈的基本操作之外，还须要应用block数组和table数字别离保留每一块蕴含的数字个数和每一个数字呈现的次数，第i块(i>=0)保留的数字范畴是[iblockSize,(i+1)blockSize-1]，那么求解栈的中位数的办法如下：

• 1、获取中位数的地位k=st.size()/2+st.size()%2;
• 2、应用sum示意以后累计的数字的个数
• 3、查找第k大的数字所在的块号i，第一个使得sum+block[i]>=k成立的就是第k大的数字所在的块号
• 4、查找第k大的数字在第i号块中的对应数字num，第i号块的第一个数字为iblockSize,让num=iblockSize，而后遍历num数字，只有sum+table[num]==k，就阐明以后的num就是第k大的数字。

提交后果

AC代码

#include <iostream>
#include <stack>
#include <string>
#include <cmath>
#include <cstring>

using namespace std;

int table[100010];
stack<int> st;

void push(int block[],int x){
    st.push(x);
    ++table[x];
    int blockSize = (int)sqrt(100001*1.0);
    ++block[x/blockSize];
}

int pop(int block[]){
    int x = st.top();
    st.pop();
    --table[x];
    int blockSize = (int)sqrt(100001*1.0);
    --block[x/blockSize];
    return x;
}

int getMedian(const int block[]){
    // 获取中位数的地位
    int k = st.size()/2+st.size()%2;
    // 累计以后曾经呈现过的数字个数
    int sum = 0;
    int blockSize = (int)sqrt(100001*1.0);
    // 查找第一个使得sum+block[i]>=k的块号i
    int i;
    for(i=0;i<blockSize;++i){
        if(sum+block[i]<k){
            sum += block[i];
        }else{
            break;
        }
    }
    // 第k大的数字在第i块中
    int num;// 保留以后遍历的数字
    int start = i*blockSize;
    int end = (i+1)*blockSize;
    for(num=start;num<end;++num){
        if(sum+table[num]<k){
            sum += table[num];
        }else{
            // 以后num就是第k大的数字
            break;
        }
    }
    return num;
}

int main() {
    int blockSize = (int)sqrt(100001*1.0);
    int block[blockSize];
    memset(block,0,sizeof(block));
    int n;
    scanf("%d",&n);
    string str;
    int num;
    for(int i=0;i<n;++i){
        cin>>str;
        if(str=="Pop"){
            if(st.empty()){
                printf("Invalid\n");
            }else{
                printf("%d\n",pop(block));
            }
        }else if(str=="Push"){
            cin>>num;
            push(block,num);
        }else{
            if(st.empty()){
                printf("Invalid\n");
            }else{
                printf("%d\n",getMedian(block));
            }
        }
    }
    return 0;
}