题意：一个长度L的管子，起点在0。n次操作，0 p表示在p的位置放上蛋糕，1表示去吃掉最近的蛋糕(如果左右都有蛋糕且距离相同，那么吃同方向的蛋糕)，问最终走了多少路程
分析：用来保存蛋糕的位置，以当前的位置进行二分查找相邻的蛋糕的位置，模拟这个过程。当然也可以用线段树单点更新维护。
收获：当结果和暴力程序跑出来的一样却WA时，想想是否遗漏了某些情况的讨论
multiset：
/************************************************* Author :Running_Time* Created Time :2015-8-22 9:31:50* File Name :C.cpp ************************************************/#include#include #include #include #include #include #include #include #include #include #include #include #include
Segment_Tree：
#includeusing namespace std;#define lson l, mid, o << 1#define rson mid + 1, r, o << 1 | 1typedef long long ll;const int N = 1e5 + 5;const int INF = 0x3f3f3f3f;struct Segment_Tree { struct Node { int mx, mn, cnt; }node[N<<2]; void push_up(int o) { node[o].mx = max (node[o<<1].mx, node[o<<1|1].mx); node[o].mn = min (node[o<<1].mn, node[o<<1|1].mn); } void build(int l, int r, int o) { if (l == r) { node[o].mx = -INF; node[o].mn = INF; node[o].cnt = 0; return ; } int mid = l + r >> 1; build (lson); build (rson); push_up (o); } void updata(int p, int c, int l, int r, int o) { if (l == r && p == l) { node[o].mx = node[o].mn = p; node[o].cnt += c; if (!node[o].cnt) { node[o].mx = -INF; node[o].mn = INF; } return ; } int mid = l + r >> 1; if (p <= mid) updata (p, c, lson); else updata (p, c, rson); push_up (o); } int query_left(int ql, int qr, int l, int r, int o) { if (ql <= l && r <= qr) { return node[o].mx; } int mid = l + r >> 1, ret = -INF; if (ql <= mid) ret = max (ret, query_left (ql, qr, lson)); if (qr > mid) ret = max (ret, query_left (ql, qr, rson)); return ret; } int query_right(int ql, int qr, int l, int r, int o) { if (ql <= l && r <= qr) { return node[o].mn; } int mid = l + r >> 1, ret = INF; if (ql <= mid) ret = min (ret, query_right (ql, qr, lson)); if (qr > mid) ret = min (ret, query_right (ql, qr, rson)); return ret; }}st;int main(void) { int T, cas = 0; scanf ("%d", &T); while (T--) { int n, m; scanf ("%d%d", &n, &m); n++; st.build (1, n, 1); ll ans = 0; int now = 1, d = 1; while (m--) { int op, p; scanf ("%d", &op); if (op == 0) { scanf ("%d", &p); p++; st.updata (p, 1, 1, n, 1); } else { int p1 = st.query_left (0, now, 1, n, 1); int p2 = st.query_right (now, n, 1, n, 1); if (p1 == -INF && p2 == INF) continue; if (p2 == INF) { ans += now - p1; if (p1 < now) d = 0; now = p1; st.updata (p1, -1, 1, n, 1); } else if (p1 == -INF) { ans += p2 - now; if (p2 > now) d = 1; now = p2; st.updata (p2, -1, 1, n, 1); } else { int dt0 = now - p1, dt1 = p2 - now; if (dt0 == dt1) { if (d == 0) { ans += dt0; now = p1; st.updata (p1, -1, 1, n, 1); } else { ans += dt1; now = p2; st.updata (p2, -1, 1, n, 1); } } else if (dt0 < dt1) { ans += dt0; now = p1; if (dt0) d = 0; st.updata (p1, -1, 1, n, 1); } else { ans += dt1; now = p2; if (dt1) d = 1; st.updata (p2, -1, 1, n, 1); } } } } printf ("Case %d: %I64d\n", ++cas, ans); } return 0;}