黑匣子

发表于 更新于 分类于 阅读次数：

Luogu P1801 黑匣子_NOI导刊2010提高（06） 题目要求一边插入，一边维护加入的元素中第i小的值，容易想到使用对顶堆 用了两个优先队列，一个放前i小的数，一个放更大的 直接放一下核心代码好了（懒懒懒

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
int M,N,I=0;
int m[200100],n;
std::priority_queue<int> less;
std::priority_queue<int,std::vector<int>,std::greater<int> > more;
int main()
{
    int M=read(),N=read();
    for(int i=1;i<=M;++i) m[i]=read();
    int i=1,j=1;
    for(;i<=N;++i){
        n=read();
        for(;j<=n;++j){
            less.push(m[j]);
        }
        while(less.size()>I+1){
            more.push(less.top());
            less.pop();
        }
        while(!more.empty() && less.size()<I+1){
            less.push(more.top());
            more.pop();
        }
        ++I;
        while(!less.empty() && !more.empty() && less.top()>more.top()){
            int x=less.top();
            less.pop();
            less.push(more.top());
            more.pop();
            more.push(x);
        }
        std::cout<<less.top()<<std::endl;
    }
    return 0;
}