题意：一个老鼠在一条长度为L的直线上跑，吃蛋糕，老鼠只能沿直线移动。开始时没有蛋糕，老鼠的初始位置是0.
有两个操作，0 x 代表在位置x添加一个蛋糕； 1 代表老鼠想吃蛋糕。老鼠每次都会选择离自己最近的点，如果两边距离相同，老鼠优先选择与自己当前移动方向相同的点。
求最终移动的总距离。
题解：线段树单点修改+查询区间端点。
设当前位置为pos，每次查询区间[0, pos]的最右端和区间[pos, L]的最左端，比较选择哪个更近。
详细题解见代码注释。
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #define lson l, m, rt << 1 #define rson m+1, r, rt << 1 | 1 #define LEFT 0 #define RIGHT 1 using std::min; using std::max; using std::abs; const int MAXN = 100010; const int INF = 1 << 30; int tr[MAXN << 2]; //标记哪个点有蛋糕 int left[MAXN << 2]; //标记区间[l, r]内有蛋糕的最左端点 int right[MAXN << 2]; //标记区间[l, r]内有蛋糕的最右端点 int N, S; int findL, findR; //标记查找到的任意区间[l, r]中有蛋糕的最左端和最右端 void PushUp( int rt ) { int lc = rt << 1; int rc = rt << 1 | 1; left[rt] = min( left[lc], left[rc] ); right[rt] = max( right[lc], right[rc] ); return; } void build( int l, int r, int rt ) //建树 { tr[rt] = 0; //每个点初始蛋糕数目为0 left[rt] = INF; right[rt] = -INF; if ( l == r ) return; int m = ( l + r ) >> 1; build( lson ); build( rson ); return; } void Update( int pos, int v, int l, int r, int rt ) //更新 { if ( l == pos && r == pos ) { tr[rt] += v; //更新该点的蛋糕数目 if ( tr[rt] == 0 ) //如果这一点没有蛋糕了 { left[rt] = INF; right[rt] = -INF; } else //如果这一点有蛋糕 { left[rt] = l; right[rt] = l; } return; } int m = ( l + r ) >> 1; if ( pos <= m ) Update( pos, v, lson ); else Update( pos, v, rson ); PushUp( rt ); return; } void Query( int L, int R, int l, int r, int rt ) //查询 { if ( L <= l && r <= R ) { findL = min( left[rt], findL ); findR = max( right[rt], findR ); return; } int m = ( l + r ) >> 1; if ( L <= m ) Query( L, R, lson ); if ( R > m ) Query( L, R, rson ); return; } int main() { int T, cas = 0; scanf( "%d", &T ); while ( T-- ) { scanf( "%d%d", &N, &S ); ++N; //原题目中pipe长度为L,编号为0-L，实际上是有(L+1)个点， //之前没注意，RE了一次，在这里我把每个点编号为1-(L+1) int curPos = 1; //当前位置 int curDirection = RIGHT; //当前方向 int sum = 0; //移动总路程 build( 1, N, 1 ); //建树 while ( S-- ) { //printf("**************curPos=%d curDir=%d ", curPos, curDirection ); int op, pos; scanf( "%d", &op ); if ( op == 0 ) { scanf( "%d", &pos ); Update( pos+1, 1, 1, N, 1 ); } else { bool find = false; int findpos; if ( curDirection == LEFT ) //如果当前方向向左 { int LL, RR; findL = INF; findR = -INF; Query( 1, curPos, 1, N, 1 ), LL = findR; //向左走，找离当前点最近的右端点 findL = INF; findR = -INF; Query( curPos, N, 1, N, 1 ), RR = findL; //向右走，找离当前点最近的左端点 if ( LL == -INF && RR == INF ) //两边都没有蛋糕 { find = false; } else if ( LL == -INF && RR != INF ) //只有右边有蛋糕 { find = true; findpos = RR; curDirection = RIGHT; } else if ( LL != -INF && RR == INF ) //只有左边有蛋糕 { find = true; findpos = LL; curDirection = LEFT; } else //两边都有蛋糕 { find = true; if ( curPos - LL <= RR - curPos ) //注意等号，两边距离相等时优先选择左边 { findpos = LL; curDirection = LEFT; } else { findpos = RR; curDirection = RIGHT; } } //printf("LEFT: "); } else { int LL, RR; findL = INF; findR = -INF; Query( curPos, N, 1, N, 1 ), RR = findL; findL = INF; findR = -INF; Query( 1, curPos, 1, N, 1 ), LL = findR; if ( LL == -INF && RR == INF ) { find = false; } else if ( LL == -INF && RR != INF ) { find = true; findpos = RR; curDirection = RIGHT; } else if ( LL != -INF && RR == INF ) { find = true; findpos = LL; curDirection = LEFT; } else { find = true; if ( curPos - LL < RR - curPos ) //注意没有等号，两边距离相等时优先选择右边 { findpos = LL; curDirection = LEFT; } else { findpos = RR; curDirection = RIGHT; } } //printf("RIGHT: "); } //printf( "findL=%d findR=%d ", findL, findR ); //printf( "findpos = %d ", findpos ); if ( find ) { sum += abs( findpos - curPos ); curPos = findpos; Update( findpos, -1, 1, N, 1 ); } } } printf( "Case %d: %d ", ++cas, sum ); } return 0; }