PTA——特殊堆栈

我不是女神ヾ 2023-10-02 16:25 18阅读 0赞

特殊堆栈 (30 分)  
堆栈是一种经典的后进先出的线性结构，相关的操作主要有“入栈”（在堆栈顶插入一个元素）和“出栈”（将栈顶元素返回并从堆栈中删除）。本题要求你实现另一个附加的操作：“取中值”——即返回所有堆栈中元素键值的中值。给定 N 个元素，如果 N 是偶数，则中值定义为第 N/2 小元；若是奇数，则为第 (N+1)/2 小元。

输入格式：  
输入的第一行是正整数 N（≤10  
5  
）。随后 N 行，每行给出一句指令，为以下 3 种之一：

Push key  
Pop  
PeekMedian  
其中 key 是不超过 10  
5  
的正整数；Push 表示“入栈”；Pop 表示“出栈”；PeekMedian 表示“取中值”。

输出格式：  
对每个 Push 操作，将 key 插入堆栈，无需输出；对每个 Pop 或 PeekMedian 操作，在一行中输出相应的返回值。若操作非法，则对应输出 Invalid。

输入样例：
    17
    Pop
    PeekMedian
    Push 3
    PeekMedian
    Push 2
    PeekMedian
    Push 1
    PeekMedian
    Pop
    Pop
    Push 5
    Push 4
    PeekMedian
    Pop
    Pop
    Pop
    Pop
    结尾无空行

输出样例：
    Invalid
    Invalid
    3
    2
    2
    1
    2
    4
    4
    5
    3
    Invalid
    结尾无空行

#include<iostream>
    #include<string>
    #include<vector>
    #include<algorithm>
    using namespace std;
    int main() {
        
    	int stack[100000];
    	int n,top = -1;
    	string str;
    	vector<int> order;
    	scanf("%d", &n);
    	for (int i = 0; i < n; i++) {
        
    		cin >> str;
    		if (str == "Push") {
        
    			scanf("%d", &stack[++top]);
    			order.insert(lower_bound(order.begin(), order.end(), stack[top]), stack[top]);
    		}
    		else if (str == "Pop"&&top >= 0) {
        
    			order.erase(lower_bound(order.begin(), order.end(), stack[top]));
    			printf("%d\n", stack[top--]);
    		}
    		else if (str == "PeekMedian"&&top >= 0)
    			printf("%d\n", order[top / 2]);
    		else
    			printf("Invalid\n");
    	}
    	return 0;
    }

[转载][Link 1]

[Link 1]: https://blog.csdn.net/qq_40946921/article/details/88130227?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163758024016780271992287%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=163758024016780271992287&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-88130227.pc_search_all_es&utm_term=%20%E7%89%B9%E6%AE%8A%E5%A0%86%E6%A0%88%20%2830%20%E5%88%86%29&spm=1018.2226.3001.4187