[PAT-A 1057]Stack

标签： PAT-A

在这里插入图片描述

题目大意:
给出一个栈的入栈出栈过程，并随时通过PeekMedian命令要求输出栈中中位数，Pop命令输出出栈的数。
当栈中没有元素时，Pop命令和PeekMedian命令都应该输出"Invalid"。

思路：
1）关于实时查询数组元素中第k大的元素。
所谓实时查询就是在查询过程中会有元素不断的添加与删除，如果每次都排序会超时，因此考虑如下策略：

1.考虑将N个元素分为sqrt(N)块，其中每块sqrt(N)个元素。则除最后一块，每一块都应该有sqrt(N)个元素。
2.元素序列中都是不超过10^5的非负整数，设置hashTable[100010]，其中hashTable[x]表示整数x的存在个数。
3.定义整型数组block[317]，其中block[i]表示第i块中存在的元素个数，加入要新增一个元素，则令block[x/316]加一，表示该块中元素多了1，同时令table[x]+1，表示整数x的当前个数+1。
4.查询第K大的数，从小到大枚举块号，利用block数组累加前i-1块元素总个数，判断加入i号块之后元素的总个数能否达到k，如果可以，说明第k大的数就在当前枚举的这个块中，此时只需要从小到大遍历该块中的每个元素，利用hashTable数组
累加元素存在的个数，直到总数累计到达k，则说明找见了第K大的数。

２）根据入栈出栈指令，对栈进行操作，push入栈，pop指令输出栈顶元素，同时对hashTable与block数组进行操作，PeekMedian输出当前栈中中间的元素，即k取中间位置进行查询。

AC代码：

//PAT_A 1040
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int maxn = 100010;
const int sqrN = 316;//分块个数
stack<int> st;
int block[sqrN], table[maxn];
void PeekMedian(int k) {
	int sum = 0, index = 0;//当前累计存在的个数，块号
	while (sum + block[index] < k) {
		sum += block[index];
		index++;
	}
	int num = index * sqrN;
	while (sum + table[num] < k) {
		sum += table[num];
		num++;
	}
	printf("%d\n", num);
	return;
}
void push(int x) {
	st.push(x);
	block[x / sqrN]++;
	table[x]++;
}
void pop() {
	int x = st.top();
	st.pop();
	block[x / sqrN]--;
	table[x]--;
	printf("%d\n", x);
}
int main() {
	int x, query;
	char cmd[20];
	fill(block, block + sqrN, 0);
	fill(table, table + maxn, 0);
	(void)scanf("%d", &query);
	for (int i = 0; i < query; i++) {
		(void)scanf("%s", cmd);
		if (strcmp(cmd, "Push") == 0) {
			(void)scanf("%d", &x);
			push(x);
		}
		else if (strcmp(cmd, "Pop") == 0) {
			if (st.empty() == true)printf("Invalid\n");
			else pop();
		}
		else {
			if (st.empty() == true)printf("Invalid\n");
			else {
				int k = st.size();
				if (k % 2 == 1)k = k / 2 + 1;
				else k /= 2;
				PeekMedian(k);
			}
		}
	}
	return 0;
}

本文链接：https://blog.csdn.net/weixin_44699689/article/details/104727244

智能推荐

模拟按键 —— 鼠标

背景之前写自动化脚本的时候总是遇到一些很尴尬的问题：跑脚本时模拟鼠标按键时，光标是真实的跑到了那个位置的，也就是说跑脚本的时候会很影响电脑的正常使用，导致不得不开一个虚拟机专门跑。另外因为光标只有一个所以很难实现多线程去同时操作多个窗口，当线程1 模拟鼠标但还没有结束时，线程2 已经开始执行模拟操作，这就导致了线程1 的模拟操作被终止了，被迫之下只能开多个虚拟机（但实在太占用性能🙄）解决...

Hibernate学习总结（一）

一、Hibernate简介一个持久层的ORM框架。ORM：Object Relational Mapping（对象关系映射）。指的是将一个Java中的对象与关系型数据库中的表建立一种映射关系，从而操作对象就可以操作数据库中的表。二、Hibernate入门 1、创建一个项目，引入jar包 hibernate用到的jar包 2、创建表 3、创建实体类 4、创建映射（*****）映射需要通过XML...

Linux系统NFS

文章目录 1. nfs简介 1.1 nfs特点 1.2 使用nfs的好处 1.3 nfs的体系组成 1.4 nfs的应用场景 2. nfs工作机制 2.1 RPC 2.2 NIS 2.3 nfs工作机制 3. exports文件的格式 4. nfs管理 5. 作业 5.1手动搭建一个nfs服务器 5.1.1开放/nfs/shared目录，供所有用户查阅资料 5.1.2 开放/nfs/upload目...

关于java中String，StringBuffer，StringBuilder的区别以及StringBuffer，StringBuilder的安全性问题

这里的结果就是正确的然后我们来看他的append方法它在前边加了一个synchronized来修饰，相当于同时只能有一个线程来访问他，这样就不会产生上边的问题但同时他的效率也就比StringBuilder低，...

Django连接现有mysql数据库

1、打开cmd后cd到项目位置 2、建立项目 django-admin startproject test2 3、编辑项目中的配置文件, mysite/settings.py ,告诉Django你的数据库连接参数和数据库名。具体的说，要提供 DATABASE_NAME , DATABASE_ENGINE , DATAB...

[PAT-A 1057]Stack

智能推荐

猜你喜欢