Fork me on GitHub

1057 Stack (30分)

发表于 | 分类于 | 次阅读
字数统计: 575 | 阅读时长 ≈ 2

题目要求我们输出栈中从小到大中间的数，考虑到有重复元素和排序，所以选择multiset，但是我们不能直接使用下标访问set元素，比如*(s.begin() + 2) 或 s[2]，都是不行的。直接遍历的话会超时，所以我们可以用以下思路：

  • 我们可以动态化地更新mid的值，比如3的时候mid = 3，2 3 的时候mid = 2，1 2 3的时候mid值是2，1 1 2 3 的时候mid = 1。
  • 我们可以用两个multiset来存放值，s1用来存放 <= mid的值，s2用来存放 > mid的值。1 2 3 的时候s1里放1 2，s2里放3，mid的值是s1的最后一个元素2，1 1 2 3 的时候s1里放1 1，s2里放2 3，mid的值是1。
  • 由于插入和删除的时候mid的值会有所变化，我们可以通过更新s1和s2里存放的值来更新mid，我们要使得s1.size() == s2.size() （这是偶数情况），或s1.size() == s2.size() + 1（这是奇数情况）。
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
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;


stack<int> s;
multiset<int> s1 , s2;
int mid = 0;

void opt(){
    if(s1.size() < s2.size()){
        multiset<int>::iterator iter = s2.begin();
        s1.insert(*iter);
        s2.erase(iter);
    }
    else if(s1.size() > s2.size() + 1){
        multiset<int>::iterator iter = s1.end();
        iter--;
        s2.insert(*iter);
        s1.erase(iter);
    }
    if(!s1.empty()){
        multiset<int>::iterator iter = s1.end();
        iter--;
        mid = *iter;
    }
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    for(int i = 0 ; i<n ; ++i){
        string c;
        cin>>c;
        if(c[1] == 'o'){
            if(s.empty()){
                cout<<"Invalid"<<endl;
            }
            else {
                if(s.top() <= mid){
                    s1.erase(s1.find(s.top()));
                }
                else s2.erase(s2.find(s.top()));
                opt();
                cout<<s.top()<<endl;
                s.pop();
            }
        }
        else if(c[1] == 'u'){
            int a;
            scanf("%d" , &a);
            s.push(a);
            if(s1.empty() || a <= mid){
                s1.insert(a);
            }
            else s2.insert(a);
            opt();
        }
        else {
            if(s.empty()){
                cout<<"Invalid"<<endl;
            }
            else {
                cout<<mid<<endl;
            }
        }
        //cout<<s1.size()<<' '<<s2.size()<<' '<<mid<<endl;
    }

}

反思：由于是一个一个元素插入或删除，所以mid的值只会移动一步，所以找到这个位置是关键，如果只用一个multiset的话，这个位置是找不到的。