在线求中位数（set）实现 TOJ3515

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <set>
  5 
  6 using namespace std;
  7 
  8 multiset<int> smin;
  9 multiset<int> smax;
 10 multiset<int>::iterator it;
 11 char arr[5];
 12 
 13 int main()
 14 {
 15     int T;
 16     scanf("%d",&T);
 17     while(T--)
 18     {
 19         int n;
 20         scanf("%d",&n);
 21         int x;
 22         int first=1;
 23         int mid;
 24         smax.clear();
 25         smin.clear();
 26         for(int i=0;i<n;i++)
 27         {
 28             int tmp;
 29             scanf("%d",&tmp);
 30             if(first)
 31             {
 32                 first=0;
 33                 mid=tmp;
 34             }
 35             else
 36             {
 37                 if(tmp>mid)
 38                 {
 39                     smax.insert(tmp);
 40                     if((smax.size())>=(smin.size()+2))
 41                     {
 42                         smin.insert(mid);
 43                         mid=*(smax.begin());
 44                         it=smax.begin();
 45                         smax.erase(it);
 46                     }
 47                 }
 48                 else
 49                 {
 50                     smin.insert(tmp);
 51                     if(smin.size()>smax.size())
 52                     {
 53                         smax.insert(mid);
 54                         it=smin.end();
 55                         it--;
 56                         mid=*(it);
 57                         smin.erase(it);
 58                     }
 59                 }
 60             }
 61         }
 62         int m;
 63         scanf("%d",&m);
 64         for(int i=0;i<m;i++)
 65         {
 66             scanf("%s",arr);
 67             if(arr[0]=='a')
 68             {
 69                 int tmp;
 70                 scanf("%d",&tmp);
 71                 if(first)
 72                 {
 73                     first=0;
 74                     mid=tmp;
 75                 }
 76                 else
 77                 {
 78                     if(tmp>mid)
 79                     {
 80                         smax.insert(tmp);
 81                         if(smax.size()>=smin.size()+2)
 82                         {
 83                             smin.insert(mid);
 84                             mid=*(smax.begin());
 85                             it=smax.begin();
 86                             smax.erase(it);
 87                         }
 88                     }
 89                     else
 90                     {
 91                         smin.insert(tmp);
 92                         if(smin.size()>smax.size())
 93                         {
 94                             smax.insert(mid);
 95                             it=smin.end();
 96                             it--;
 97                             mid=*(it);
 98                             smin.erase(it);
 99                         }
100                     }
101                 }
102             }
103             else if(arr[0]=='m')
104             {
105                 cout<<mid<<endl;
106             }
107         }
108     }
109     return 0;
110 }
View Code