pat 甲级 L3-002. 堆栈

L3-002. 堆栈

时间限制

200 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

大家都知道“堆栈”是一种“先进后出”的线性结构，基本操作有“入栈”（将新元素插入栈顶）和“出栈”（将栈顶元素的值返回并从堆栈中将其删除）。现请你实现一种特殊的堆栈，它多了一种操作叫“查中值”，即返回堆栈中所有元素的中值。对于N个元素，若N是偶数，则中值定义为第N/2个最小元；若N是奇数，则中值定义为第(N+1)/2个最小元。

输入格式：

输入第一行给出正整数N（<= 10 ⁵ ）。随后N行，每行给出一个操作指令，为下列3种指令之一：

Push key
Pop
PeekMedian

其中Push表示入栈， key 是不超过10 ⁵ 的正整数；Pop表示出栈；PeekMedian表示查中值。

输出格式：

对每个入栈指令，将 key 入栈，并不输出任何信息。对每个出栈或查中值的指令，在一行中打印相应的返回结果。若指令非法，就打印“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

思路：模拟堆栈+BIT

首先push,pop操作可以先用一个堆栈来存储模拟，并且需要对BIT进行更新，譬如要push一个数x，那么在BIT的第x个位置处+1，代表该位置上存有这个数,同理,pop一个数x时，在BIT的位置x处-1，消掉该数的记录。遇到查中值时即可对BIT二分搜索,譬如要查第n/2个数，若这个数数值为x，那么对BIT从1到x所有位置进行取和的值就是n/2。

AC代码：

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<vector>

#include<string>

#include<iomanip>

#include<map>

#include<stack>

#include<set>

using namespace std;

#define N_MAX 100000+2

#define INF 0x3f3f3f3f

int n;

int bit[N_MAX + ];

int sum(int i) {

  int s = ;

  while (i>) {

    s += bit[i];

    i -= i&-i;

  }

  return s;

}

void add(int i,int x) {

  while (i<=N_MAX) {//!!!!!!!!

    bit[i] += x;

    i += i&-i;

  }

}

bool C(int x,int n) {

  if (sum(x) >= n)return true;

  else return false;

}

int st[N_MAX];

int main() {

  while (scanf("%d", &n) != EOF) {

    memset(bit, , sizeof(bit));

    int num = ;

    while (n--) {

      char s[]; scanf("%s",s);

      if (s[] == 'o') {

        if (num == ) { puts("Invalid"); continue; }

        printf("%d\n", st[num-]);

        add(st[num-], -);

        num--;

      }

      else if (s[] == 'u') {

        int a; scanf("%d", &a);

        add(a, ); st[num++]=a;

      }

      else if (s[] == 'e') {

        if (num == ) { puts("Invalid"); continue; }

        int lb = , ub = N_MAX;//!!!

        int cnt = num;

        if (cnt & )cnt = (cnt + ) / ;

        else cnt /= ;

        while (ub - lb > ) {

          int mid = (lb + ub) >> ;

          if (C(mid, cnt))ub = mid;

          else lb = mid;

        }

        printf("%d\n", ub);

      }

    }

  }

  return ;

}