知识点:链表
难度:4
昨天学习了链表离线倒序算法,今天练习一下,这个题一看是动态的中位数问题,但是还是可以用链表来离线处理,就是输入的时候储存一下中间到第几个数需要我们来输出中位数,其它的原来的差不多,排序,记录输入序列中的元素在排完序后的序列中是第几个,如果是偶数个的话,那么我们无脑选中间的两个数的前一个就行,因为是我们排过序的,
今天做这个题又理解了一下,链表来处理这种问题的瓶颈在于排序,因为排序是nlogn,而后面的处理都是O(n),因为每次操作我们可以通过O(1)来得到我们想要得到的元素的地址,具体情况就是根据题目就行了,所以李煜东才会写的这种方法的瓶颈在于排序
本来可以30分钟过了这个题,结果硬是因为75行的i写成n多看了20多分钟的代码,写成n是显然不对的
- #include
-
- using namespace std;
-
- const int N = 110005;
-
- struct node {
- int val;
- int pre, nxt;
- } c[N];
-
- int tot, head, tail;
-
- void init() {
- tot = 2;
- head = 1; tail = 2;
- c[1].nxt = 2;
- c[2].pre = 1;
- }
-
- void insert(int val) {
- int q = ++tot;
- c[q].val = val;
- c[q].pre = c[2].pre;
- c[q].nxt = 2;
- c[c[q].pre].nxt = q;
- c[2].pre = q;
- }
-
- void remove(int p) {
- c[c[p].pre].nxt = c[p].nxt;
- c[c[p].nxt].pre = c[p].pre;
- }
-
- int main() {
- int n;
- cin >> n;
- int rec = n;
- pair<int, int> a[N];
- for (int i = 1; i <= n; i++) {
- cin >> a[i].first;
- a[i].second = i;
- }
- int m;
- cin >> m;
- int Hash[N] = {};
- while (m--) {
- string op;
- cin >> op;
- if (op == "add") {
- int x;
- cin >> x;
- n++;
- a[n] = make_pair(x, n);
- } else {
- Hash[n]++;
- }
- }
- sort(a + 1, a + n + 1);
- init();
- int b[N];
- for (int i = 1; i <= n; i++) {
- insert(a[i].first);
- b[a[i].second] = i + 2;
- }
- int pos;
- if (n % 2) {
- pos = 2 + (n + 1) / 2;
- } else {
- pos = 2 + n / 2;
- }
- vector<int> ans;
- for (int i = n; i >= rec; i--) {
- while (Hash[i]--) ans.push_back(c[pos].val);
- if (i % 2) {
- if (pos <= b[i]) pos = c[pos].pre;
- } else {
- if (b[i] <= pos) pos = c[pos].nxt;
- }
- remove(b[i]);
- }
- reverse(ans.begin(), ans.end());
- for (int i = 0; i < (int) ans.size(); i++) {
- cout << ans[i] << endl;
- }
- return 0;
- }