动态中位数
刚开始的思路是先开一个vector数组，每次插入数值时先排序，使用sort排序时间复杂度为O( NlogN ),
由于最多有1000组数据且每组数据最多有9999个数，假如使用这种方法的话很有可能会超时。
由此换种思路，使用查询+插入的方式，在插入前保证已有的数组是有序的就可以了，这样时间复杂度就变为O（N）
了。
其中，查询使用lower_bound，这个方法使用了二分法，时间复杂度低，插入使用insert，时间复杂度为O(N）。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <climits> 5 #include <vector> 6 using namespace std; 7 vector<int> a; 8 int main(){ 9 int p; 10 scanf("%d", &p); 11 while(p --){ 12 int id, m, cnt = 0, sum = 0; 13 a.clear(); 14 scanf("%d%d", &id, &m); 15 printf("%d %d ", id, (m + 1) / 2); 16 a.push_back(INT_MIN); //先将数组的第一个数设为最小，以后不论什么数字都会在这一个数字的后面 17 for(int i = 1; i <= m; i ++){ 18 int temp; 19 scanf("%d", &temp); 20 int pos = lower_bound(a.begin(), a.end(), temp) - a.begin(); 21 a.insert(a.begin() + pos, temp); 22 if(i % 2 == 1){ 23 printf("%d ", a[(a.size() + 1) / 2]); 24 cnt ++; 25 sum ++; 26 if(cnt == 10){ //格式控制 27 cout << endl; 28 cnt = 0; 29 } 30 } 31 } 32 if((m + 1) / 2 % 10 != 0) 33 cout << endl; 34 } 35 return 0; 36 }