郭大侠与线上游戏

Time Limit: 6000/2000MS (Java/Others) Memory Limit: 125535/65535KB (Java/Others)

Submit Status

title

曾在网络游戏告白，但对方是假冒女生的人妖，而对此有阴影的郭大侠，坚持把游戏和现实分得清清楚楚。有一天竟被网络游戏中的女玩家告白了，虽然在游戏中接受了亚子的表白而结婚，但仍然不敢确信亚子就是真真正正的女生。终于有一天，卢西安所属四人公会的富豪会长决定举行线下聚会，结果发现四个人居然都是同一所高中的学生，甚至另外三人都是真真正正的可爱女孩子。

郭大侠还没完全接受这个事实时，他们发现亚子居然是重度的现实游戏混淆症患者，不仅在现实生活中用游戏角色名字“卢西安”叫人，还旁若无人黏住英骑身上。为了让亚子能够恢复正常，四人的游戏生活延续至学校。

……

今天，拯救亚子的计划是玩游戏！

这个游戏是这样的~

有一个像队列一样的东西，你可以push一个元素到这个队列的尾部，也可以pop掉这个队列的第一个元素

现在问题来了，这个队列中位数是多少呢？

中位数的定义为该队列升序排序后第k/2+1个的数的值，k为这个队列的大小

Input

第一行一个

接下来

1 x，向这个队列推入一个数x

2，弹出这个队列的第一个数

3，查询这个队列的中位数是多少

保证队列中的每个数都不一样哦~

Output

对于每一个询问输出答案。

保证有解~

Sample input and output

Sample Input	Sample Output
61 231 4323	244

思路：

侠与线上游戏

一开始用卿学姐的方法，，，然后搞半天写不出来，，写炸了。。。

无奈之下之后和b题一样自己想了。。

然后发现不论删除加入一个数，数列中位数的位置就在原中位数的附近，要么左移要么右移，要么不动，，所以这样就可以分类讨论下就好了。。。。

Ps：发现set真是好用，自动排好序，，

对于要加入删除的数用一个队列记录就好了，，，

恩，就这样就可以了

1 #include 
        
          2 #include 
         
           3 #include 
          
            4 #include 
           
             5 #include 
            
              6 #include 
             
               7 #include 
              
                8 #include 
                9 #include 
                
                 10 #include 
                 
                  11 #include 
                  
                   12 #include 
                   
                    13 14 #define PI acos((double)-1)15 #define E exp(double(1))16 using namespace std;17 set
                    
                     p;18 queue
                     
                      q;19 set
                      
                       ::iterator it,tit;20 int main (void)21 {22 int t;23 cin>>t;24 while(t--)25 {26 int a,b;27 scanf("%d",&a);28 if(a==1)29 {30 scanf("%d",&b);31 p.insert(b);32 q.push(b);33 if(p.size()==1)34 {35 it=p.begin();36 continue;37 }38 if(b > (*it) && p.size()%2==0)39 it++;40 if (b < (*it) && p.size()%2!=0)41 it--;42 }43 else if(a==2)44 {45 tit=p.find(q.front());46 if(*tit > *it && p.size()%2==0)47 it--;48 else if(*tit < *it && p.size()%2!=0)49 it++;50 else if(*tit==*it && p.size()%2==0)51 it--;52 else if(*tit==*it && p.size()%2!=0)53 it++;54 q.pop();55 p.erase(tit);56 }57 else58 {59 if(p.size()==1)60 it=p.begin();61 printf("%d\n",*it);62 }63 }64 return 0;65 }

View Code

转载于:https://www.cnblogs.com/weeping/p/5456126.html

你可能感兴趣的文章