oazestar @ 2019-09-24 21:40:28
自己打的代码：
(简写)
vector<int> v;
n = in; a = in;
outn(a); v.pb(a);
for (int i = 2; i <= n; i += 2) {
a = in; v.ins(upper_bound(v.begin(), v.end(), a), a);
a = in; v.ins(upper_bound(v.begin(), v.end(), a), a);
outn(v[i / 2]);
}然后一排
于是看了一眼题解
改了一下
n = in;
for (int i = 1; i <= n; ++i) {
a = in; v.ins(upper_bound(v.begin(), v.end(), a), a);
if (i & 1) outn(v[i / 2]);
}于是
这是什么复杂度概念orz
by kevin006 @ 2019-09-24 21:43:36
同求
by yzm123 @ 2019-09-24 21:49:46
@辰殷yu 这种东西一般就是玄学问题了
by nth_element @ 2019-09-24 21:52:00
同求
by qwqqwq_qwqqwq @ 2019-09-24 21:52:47
vector::insert的复杂度上界是O(n)，取决于插入位置。
by 斗神_君莫笑 @ 2019-09-24 21:58:02
@辰殷yu 你告诉我严格意义上vector支持insert？
by 斗神_君莫笑 @ 2019-09-24 21:58:19
@辰殷yu 写容器的人就没想过提供insert操作
by oazestar @ 2019-09-25 18:32:40
@斗神_君莫笑 emmm但是可以用不是吗[/doge]
by oazestar @ 2019-09-25 18:33:47
@qwqqwq_qwqqwq 那两个两个的插入……是真的会慢吗？_(:3
by oazestar @ 2019-09-25 18:33:55
@yzm123 233333
by 斗神_君莫笑 @ 2019-09-25 21:04:53
@辰殷yu 其实讲真deque还重载了[]，然而有几个人用呢？