[数据结构与算法]1057 Stack

目录

解题思路

AC代码

解题思路

虽然题目的名字是栈，但是这题和栈的关系很小，甚至我都没有用到stack这个数据结构，而是用vector<int>的pop_back()来模拟栈的弹出。

主要考察的是：在线查询，也就是查询过程中库中的元素可能因为插入删除或修改而发生改变。具体来说就是：查询序列中第K大的元素是什么。

这里用到了分块思想来降低查找的复杂度，块的大小是总元素个数开平方的向下取整，这个需要记住。

具体的思想是：先确定第K个元素在哪个块，再从块的第一个元素起遍历来找到这个元素。

两个重要的数据结构如下

int mycount[maxn+1] = {0};//count[x]表示x的数量
int block[BLOCK_NUM+1] = {0};//block[x]表示第x+1块有多少数据 

易错点

加入元素的时候，上述3个数据结构都要增加，不容易忘记

mystack.push_back(x);
mycount[x]++;
block[x/BLOCK_SIZE] ++; 

弹出元素的时候，往往就把后两个忘记了

mycount[mystack[mystack.size()-1]]--;//非常容易漏掉
block[(mystack[mystack.size()-1])/BLOCK_SIZE]--; 
mystack.pop_back();

AC代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<utility>
#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9;//10的9次方 
const double eps = 1e-3;

const int maxn = 100000;
const int BLOCK_SIZE = 316;
const int BLOCK_NUM = maxn/316;

vector<int> mystack;  

int mycount[maxn+1] = {0};//count[x]表示x的数量
int block[BLOCK_NUM+1] = {0};//block[x]表示第x+1块有多少数据 

//12 sqrt(12) = 4
//BLOCK_SIZE = 4
//BLOCK_NUM = 3

int main(){
		
	int n;//操作的数量
	char s[10];//读入的操作名称
	int x;//读入的元素 
	
	scanf("%d",&n);
	while(n--){
		scanf("%s",s);
		if(!strcmp(s,"PeekMedian")){
			if(mystack.size()==0){
				printf("Invalid\n");
				continue;
			}else{
				int size = mystack.size();//得到当前栈中数字的数量 
				int idx;//第idx大的数是我们想要的
				if(size%2==0)idx = size/2;
				else idx = (size+1)/2;
				int sum = 0;
				int out = false;//用于跳出 
				for(int i=0;i<=BLOCK_NUM;i++){
					if(out)break;
					sum += block[i];
					if(sum>=idx){
						int no = sum - block[i];
						for(int j=i*BLOCK_SIZE;j<(i+1)*BLOCK_SIZE;j++){
							if(out)break;
							if(mycount[j]>0){
								int temp = mycount[j];
								while(temp--){
									no ++;
									if(no == idx){
										printf("%d\n",j);
										out = true;
										break;
									}
								}
							}
						}
					}
				} 
			}
		}
		
		if(!strcmp(s,"Pop")){
			if(mystack.size()==0){
				printf("Invalid\n");
				continue;
			}else{
				printf("%d\n",mystack[mystack.size()-1]);
				mycount[mystack[mystack.size()-1]]--;//非常容易漏掉
				block[(mystack[mystack.size()-1])/BLOCK_SIZE]--; 
				mystack.pop_back();
				continue;
			}
		}
		
		if(!strcmp(s,"Push")){
			scanf("%d",&x);
			mystack.push_back(x);
			mycount[x]++;
			block[x/BLOCK_SIZE] ++; 
		}
	} 
	
	
	return 0; 
}