个人练习-PAT甲级-1057 Stack_综合

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805417945710592

摸了两天，深感惭愧。。。今天碰到的第一题就卡住了，还是看了柳神解答才会的。因为query次数多，如果每次都排序的话，一定会超时。贫瘠的脑袋没想出好方法，参考了解答后学到了新的数据结构：树状数组。

树状数组的详细介绍参考：https://www.cnblogs.com/xenny/p/9739600.html

完整代码

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>using namespace std;const int maxn = 100005;vector<int> st;
int c[maxn];int lowbit(int x) {
    return x & (-x);
}void update(int i, int k) {
    while (i <= maxn) {
    c[i] += k;i += lowbit(i);}
}
int getsum(int i) {
    int ret = 0;while (i > 0) {
    ret += c[i];i -= lowbit(i);}return ret;
}void Push() {
    int key;scanf("%d", &key);st.push_back(key);update(key, 1);
}void Pop() {
    if (st.size() == 0) {
    printf("Invalid\n");return;}int tmp = st.back();st.pop_back();update(tmp, -1);printf("%d\n", tmp);
}void PeekMedian() {
    if (st.size() == 0) {
    printf("Invalid\n");return;}int left = 1, right = maxn, mid, k = (st.size() + 1) / 2;while (left < right) {
    mid = (left + right) / 2;if (getsum(mid) >= k)right = mid;elseleft = mid + 1;}printf("%d\n", left);}int main() {
    int N;scanf("%d", &N);for (int i = 0; i < N; i++) {
    char str[11];scanf("%s", str);if (str[1] == 'u')Push();else if (str[1] == 'o')Pop();elsePeekMedian();}return 0;
}

下面介绍树状数组的相关函数
当数组中某一元素a[i]更新时，树状数组c[]中可能被影响的元素有c[i+2^k],c[(i+2^k)+2^k]等，要对它们依次更新。

void update(int i, int k){
    while (i <= maxn){
    c[i] += k;i += lowbit(i);}
}

其中lowbit()函数是用来计算2^k的，k是i的二进制从最低位到最高位连续0的长度。详见树状数组的文章。

int lowbit(int x){
    return x & (-x);
}

实现a[]数组的前i位求和的话就是sum=c[i]+c[i-2^k1]+c[(i-2^k1)-2^k2]...

void getsum(int i){
    int ret = 0;while (i > 0){
    ret += c[i];i -= lowbit(i);}return ret;
}

再结合本题栈的应用，我们用c[i]=1表示栈里有i这个数，c[i]=0表示栈里没有有i这个数。每次push和pop时更新数组c[]

void Push(){
    int key;scanf("%d", &key);st.push_back(key);update(key, 1);
}void Pop(){
    if (st.size() == 0){
    printf("Invalid\n");return;}int tmp = st.back();st.pop_back();update(tmp, -1);printf("%d\n", tmp);
}

用二分法查找，第(st.size()+1) / 2大的数，那么就是找到一个i，使得树状数组前i项和为(st.size()+1) / 2，因为c[]中为1就是有，0就是无。使用二分法查找即可。

void PeekMedian(){
    if (st.size() == 0){
    printf("Invalid\n");return;}int left = 1, right = maxn, mid, k = (st.size()+1) / 2;while (left < right){
    mid = (left + right) / 2;if (getsum(mid) >= k)right = mid;elseleft = mid + 1;}

感想：学到了新的数据结构呢~啊还是太菜了。。。单独学树状数组的时候感觉懂了，单独看题目也看懂了题意，但是如何把树状数组用到这个题目里还一下子没有想明白，是边写边想通的——为什么每次push和pop的update传入的k都是1呀——哦，原来1就是有，0就是无。实际上树状数组的文章还挺长，没全部看完，树状数组的应用是有很多的，以后有机会要再看看。