signed

QiShunwang

“诚信为本、客户至上”

PAT (Advanced Level) 1057 Stack (30 分)

2021/6/3 16:09:29   来源:

在这里插入图片描述
在这里插入图片描述
题目概述:
给一个栈,实现push pop 和求中位数。

解法一:简单模拟排序

//简单模拟的思路看看多少分?
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    stack<int> s;
    string action;
    for(int i = 0; i < n; i++)
    {   
        cin >> action;
        if(action == "Pop")
        {   
            if(s.empty())
            {
                printf("Invalid\n");
                continue;
            }
            cout << s.top() << endl;
            s.pop();
        }
        else if(action == "Push")
        {
            int num;
            cin >> num;
            s.push(num);
        }
        else if(action == "PeekMedian")
        {   
            if(s.empty())
            {
                printf("Invalid\n");
                continue;
            }
            vector<int> v;
            stack<int> s1;
            s1 = s;
            int len = s.size();
            while(!s1.empty())
            {
                v.push_back(s1.top());
                s1.pop();
            }
            sort(v.begin(), v.end());
            printf("%d\n", v[(len - 1) / 2 ]);
        }
    }
    return 0;
}

在这里插入图片描述
果不其然,三个超时,接下来想想如何优化寻中位数的过程,思考ing

解法二:树状数组

这种解法采用的是二进制方式,具体步骤我尚未能参悟。。。

#include <cstdio>
#include <stack>
#define lowbit(i) ((i) & (-i))
const int maxn = 100010;
using namespace std;
int c[maxn];
stack<int> s;
void update(int x, int v) {
    for(int i = x; i < maxn; i += lowbit(i))
        c[i] += v;
}
int getsum(int x) {
    int sum = 0;
    for(int i = x; i >= 1; i -= lowbit(i))
        sum += c[i];
    return sum;
}
void PeekMedian() {
    int left = 1, right = maxn, mid, k = (s.size() + 1) / 2;
    while(left < right) {
        mid = (left + right) / 2;
        if(getsum(mid) >= k)
            right = mid;
        else
            left = mid + 1;
    }
    printf("%d\n", left);
}
int main() {
    int n, temp;
    scanf("%d", &n);
    char str[15];
    for(int i = 0; i < n; i++) {
        scanf("%s", str);
        if(str[1] == 'u') {
            scanf("%d", &temp);
            s.push(temp);
            update(temp, 1);
        } else if(str[1] == 'o') {
            if(!s.empty()) {
                update(s.top(), -1);
                printf("%d\n", s.top());
                s.pop();
            } else {
                printf("Invalid\n");
            }
        } else {
            if(!s.empty())
                PeekMedian();
            else
                printf("Invalid\n");
        }
    }
    return 0;
}

总结:
好好参悟树状数组的update和getsum函数