A1057Stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<vector>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100001;
const int maxb = 317;
int table[maxn], block[maxb];
int n, cnt;
int main()
{
memset(table, 0, sizeof(table));
memset(block, 0, sizeof(block));
cin >> n;
stack<int> st;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
if (s == "Pop")
{
if (st.empty())
{
cout << "Invalid\n";
}
else
{
int num = st.top();
st.pop();
table[num]--;
//算块号
block[num / 316]--;
cout << num << endl;
}
}
else if (s == "PeekMedian")
{
if (st.empty())
{
cout << "Invalid\n";
continue;
}
int median = (st.size() + 1) / 2;
int sum = 0, b = 0;//b块号
while (sum + block[b] < median)
{
sum += block[b++];
}
int index = b * 316;
while (sum + table[index] < median)
{
sum += table[index++];
}
cout << index << endl;
}
else
{
int num;
cin >> num;
st.push(num);
table[num]++;
block[num / 316]++;
}
}
}
这道题使用了分块的思想，很巧妙，注意：
在取中位数时，可以使用while，更方便快捷
输出中位数直接输出index，table[index]代表的时index的个数
用sum来表示之前块的个数，然后直接从所属块第一个开始查，我之前是算出median是第几个后，企图计算出在b块的第几个，不记录sum的话，没法算，要么就算个前缀和数组，随时查，要么就临时记录