嗯...

 

题目链接：https://www.luogu.org/problem/P1168

 

这道题暴力是肯定不行的，所以说要用优先队列来维护...

 

思路：

定义一个大根堆，一个小根堆，首先将第一个数随便放进一个堆（这里我们把它放入小根堆），然后再看下一个数，如果这个数比小根堆的堆顶大，那么就把它放入小根堆，否则将它放入大根堆。注意大小根堆的元素个数不能超过2（即不能>1），如果超过，则将元素多的那个堆的堆顶元素压入另一个堆，这样我们就维护了一个类似单调递增的序列，而这道题又比较水，只讨论了奇数个元素的情况，所以最终的答案就是元素较多的堆的堆顶。（下面附一张图，但我感觉不是很好，其实就是一个单调递增的序列...

细节：

第28行到第38行不能写成：

  if(q1.size() - q2.size() > 1){ q2.push(q1.top()) ; q1.pop(); }

　if(q2.size() - q1.size() > 1){ q1.push(q2.top()); q2.pop(); }  

这样的话在pop的之后改变了size的大小...在执行下一条语句还可能合法，然后会....

 

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5  6 using namespace std; 7  8 priority_queue 
          
            q1; 9 priority_queue
           

, greater

> q2;10 int n, a;11 12 int main(){13 scanf("%d", &n);14 for(int i = 1; i <= n; i++){15 scanf("%d", &a);16 if(i == 1){17 printf("%d\n", a);18 q2.push(a);19 continue;20 }21 else{22 if(a < q2.top()) q1.push(a);23 else if(a > q2.top()) q2.push(a); 24 else{25 if(q1.size() < q2.size()) q1.push(a);26 else q2.push(a);27 }28 if(q1.size() - q2.size() > 1 || q2.size() - q1.size() > 1){29 if(q1.size() > q2.size()){30 q2.push(q1.top()) ;31 q1.pop();32 }33 else{34 q1.push(q2.top());35 q2.pop();36 }37 }38 }39 if(i % 2 && q2.size() > q1.size()) printf("%d\n", q2.top());40 else if(i % 2 && q1.size() > q2.size()) printf("%d\n", q1.top());41 }42 return 0;43 }