UESTC 1339 郭大侠与线上游戏

题目地址  http://acm.uestc.edu.cn/#/problem/show/1339

这道题，是求中位数，以前也有一道中位数的题目卡的我要死，这次这道题我依旧没有办法自己做出来，找了题解才明白怎么做，但是现在才开始分析为什么要这样做。

我一开始的想法很简单，直接用一个vector来模拟这题目，但是排序很耗费时间，一共一百万组操作，我就假设我里面五十万个数字，然后一直快排，就达到3e8的运算量了。所以会TLE。

我们要压缩这个复杂度，我们发现中位数的定义，就是n个数字排序后的第n/2+1个，我们要做的就是维护他就行了。

1，所以我们开两个set，一个L一个U，L里面放小于中位数的，U里面放大于等于中位数的，增加数字，判断加入L还是U，并且如果U的元素个数比L的元素个数多2，就把U里面最小的放入L中并删除。

2，删除操作也是这样。也是学到新东西了，删除后比如L有2个元素，U有1个，那么我们可以用rbegin来把L里面最大的元素放入U中，即U.insert（L.rbegin()），当然，自己开迭代器找好位置来赋值也是可以的。

3，删除的时候我们是要删除队列里面的第一个元素，那么我们先从第一个数t从队列里面取出来，判断下他在L还是在U，然后删除嘛，但是set容器中find的复杂度是O（n）的，所以用find还过不了，所以我们应该用L.lower_bound(t)，这样就可以知道他的位置了。

4，set的size是unsignedint类型，如果相减是负数那么就会变成很大的数字，所以第53行的错误一开始没找出来。所以尽量遵循能加就不减，能乘就不除吧。

5，分析一下这种方法复杂度，代码里面最大的处理常数是10（进入ope1，然后进入else，然后进入if），对于这道题目一百万的处理，也就是最多也才到一千万的处理（其实还有set里面增加减少是logn的次数没有考虑），不考虑常数（不卡常）其实就是维护中位数，近似于O（n）的复杂度，这样还不能过那就太丧心病狂了。相比于上面是n * nlogn快了不知道多少倍。

代码如下：

#include<set>
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
int main()
{int n, ope, t;set <int> l, u;set <int>::iterator iter;queue <int> q;cin >> n;while(n--){scanf("%d", &ope);if(ope == 1){scanf("%d", &t);q.push(t);if(u.size() == 0 || t >= *u.begin()){if(l.size() == u.size())u.insert(t);else{u.insert(t);l.insert(*u.begin());u.erase(u.begin());}}else{if(l.size() == u.size()){l.insert(t);iter = l.end();iter--;u.insert(*iter);l.erase(iter);}elsel.insert(t);}}else if(ope == 2){t = q.front();q.pop();if(t < *u.begin())l.erase(l.lower_bound(t));elseu.erase(u.lower_bound(t));if(u.size() > l.size() + 1){l.insert(*u.begin());u.erase(u.begin());}else if(l.size() > u.size()){iter = l.end();iter--;u.insert(*l.rbegin());l.erase(iter);}}elseprintf("%d\n", *u.begin());}return 0;
}