PAT甲级1057. Stack
题意：
堆栈是最基础的数据结构之一，它基于“先进先出”（LIFO）的原理。基本操作包括Push（将元素插入顶部位置）和Pop（删除顶部元素）。现在你应该实现一个额外的操作堆栈：PeekMedian -
返回堆栈中所有元素的中间值。对于N个元素，如果N是偶数，则将中值定义为（N / 2）个最小元素，或者如果N是奇数则将其定义为（（N + 1）/ 2）。
输入规格：
每个输入文件包含一个测试用例。对于每种情况，第一行包含正整数N（<= 105）。然后N行跟随，
每个都包含以下3种格式之一的命令：
按键
流行的
PeekMedian
其中key是正整数，不超过105。
输出规格：
对于每个Push命令，将密钥插入堆栈并输出任何内容。对于每个Pop或PeekMedian命令，在一行中打印相应的返回值。如果命令无效，
打印“无效”。
思路：
树状数组 参考于：
PAT1057.Stack (30)
树状数组
ac代码：
C++
// pat1057.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<stdio.h>
#include<map>
#include<cmath>
#include<unordered_map>
using namespace std;
//树形数组
const int maxn = 1e5 + 5;
int c[maxn];
int lowbit(int i) //count 2^k, (k 为数字二进制末尾0的个数）
{
return i & (-i);
}
void add(int pos, int value)
{
while (pos < maxn)
{
c[pos] += value;
pos += lowbit(pos);
}
}
int sum(int pos)
{
int res = 0;
while (pos > 0)
{
res += c[pos];
pos -= lowbit(pos);
}
return res;
}
int find(int value)
{
int l = 0, r = maxn - 1, median, res;
while (l < r - 1)
{
if ((l + r) % 2 == 0)
{
median = (l + r) / 2;
}
else
{
median = (l + r - 1) / 2;
}
res = sum(median);
if (res < value)
{
l = median;
}
else
{
r = median;
}
}
return l + 1;
}
int main()
{
int n;
scanf("%d", &n);
int stack[maxn], top = 0, pos;
memset(c, 0, sizeof(c));
char oper[20];
while(n--)
{
scanf("%s", oper);
if (oper[1] == 'o') //pop
{
if (top == 0)
{
printf("Invalid\n");
continue;
}
int out = stack[top];
add(out, -1);
printf("%d\n", stack[top--]);
}
else if (oper[1] == 'e') //peekmedian
{
if (top == 0)
{
printf("Invalid\n");
continue;
}
int res;
if (top % 2 == 0) res = find(top / 2);
else res = find((top + 1) / 2);
printf("%d\n", res);
}
else if (oper[1] == 'u') //push
{
scanf("%d", &pos);
stack[++top] = pos;
add(pos, 1);
}
else
{
printf("Invalid\n");
}
}
return 0;
}