当前位置: 代码迷 >> 综合 >> PAT1057 Stack (30)(树状数组)
  详细解决方案

PAT1057 Stack (30)(树状数组)

热度:30   发布时间:2024-01-16 13:21:11.0

题意:

模拟一个栈,要求可以输出中位数。

思路:

这题还是有点意思,看题意就知道会卡时间复杂度,想着用multiset试一下发现果然有几个点过不去,后面就没想出来。实际这题应该用树状数组做:

  • Push x:就update(x,1),就是树状数组的区间更新,c[i]+=1,说明值为i的数出现并更新与其相关的数
  • Pop:就update(x,-1),c[i]-=1,将值为i的数以及和它相关的数更新
  • PeekMedian:用二分查找中位数,每次用getsum(i)求得前i个数中实际出现了几个数,与中位数k比较即可
#include<bits/stdc++.h>
#define lowbit(i) ((i)&(-i))
using namespace std;
const int INF = 0xfffff;
const int maxn = 100050;
stack<int> s;
int c[maxn];void update(int x, int v) {for (int i = x; i < maxn; i += lowbit(i))c[i] += v;
}int getsum(int x) {int sum = 0;for (int i = x; i >= 1; i -= lowbit(i))sum += c[i];return sum;
}void peekMid() {//二分求下界int left = 1, right = maxn, k = (s.size() + 1) / 2;while (left < right) {int mid = (left + right) / 2;if (getsum(mid) >= k)right = mid;elseleft = mid + 1;}printf("%d\n", left);
}int main() {int n,temp;scanf("%d", &n);char str[15];while (n--) {scanf("%s", str);if (str[1] == 'u') {scanf("%d", &temp);s.push(temp);update(temp, 1);} else if (str[1] == 'o') {if (!s.empty()) {temp = s.top();s.pop();update(temp, -1);printf("%d\n", temp);} elseprintf("Invalid\n");} else {if (!s.empty()) {peekMid();} elseprintf("Invalid\n");}}return 0;
}

 

  相关解决方案