关于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 号块的第一个数字为 i blockSize, 让 num=iblockSize，而后遍历 num 数字，只有 sum+table[num]==k，就阐明以后的 num 就是第 k 大的数字。

#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;
}

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

题目粗心

算法思路

提交后果

AC 代码