Prelude
题目传送门：
Solution
按照题意模拟即可。
维护一个优先队列，里面装的是正在运营中的出租车，关键字是乘客的下车时间。 维护一个线段树，第\(i\)个位置表示第\(i\)个房子前面有没有停放出租车，这样在有人需要打车的时候可以快速找到离她最近的车的位置。 对每个房子维护一个堆，里面装的是停在这个房子前面的出租车，关键字是出租车的编号和上一个乘客下车的时间，上一个乘客下车越早，等待时间越长。 然后模拟时间的流逝就可以了，代码非常好写。Code
#include#include #include #include #include #include #include using namespace std;typedef long long ll;const int MAXN = 200010;const int INF = 0x3f3f3f3f;int _w;int n, k, m, x[MAXN], a[MAXN], b[MAXN];ll t[MAXN];namespace SGT { int sumv[MAXN<<2], ql, qr, qv; void _add( int o, int L, int R ) { sumv[o] += qv; if( L == R ) return; int M = (L+R)/2, lc = o<<1, rc = lc|1; if( ql <= M ) _add(lc, L, M); else _add(rc, M+1, R); } void add( int p, int v ) { ql = p, qv = v; _add(1, 1, n); } void _queryl( int o, int L, int R ) { if( L >= ql && R <= qr ) { if( !sumv[o] ) return; while( L != R ) { int M = (L+R)/2, lc = o<<1, rc = lc|1; if( sumv[lc] ) o = lc, R = M; else o = rc, L = M+1; } qv = L; } else { int M = (L+R)/2, lc = o<<1, rc = lc|1; if( ql <= M && !qv ) _queryl(lc, L, M); if( qr > M && !qv ) _queryl(rc, M+1, R); } } int queryl( int l, int r ) { ql = l, qr = r, qv = 0; _queryl(1, 1, n); return qv; } void _queryr( int o, int L, int R ) { if( L >= ql && R <= qr ) { if( !sumv[o] ) return; while( L < R ) { int M = (L+R)/2, lc = o<<1, rc = lc|1; if( sumv[rc] ) o = rc, L = M+1; else o = lc, R = M; } qv = L; } else { int M = (L+R)/2, lc = o<<1, rc = lc|1; if( qr > M && !qv ) _queryr(rc, M+1, R); if( ql <= M && !qv ) _queryr(lc, L, M); } } int queryr( int l, int r ) { ql = l, qr = r, qv = 0; _queryr(1, 1, n); return qv; }}struct Node { ll t; int id; Node() {} Node( ll t, int id ): t(t), id(id) {} bool operator<( const Node &rhs ) const { return t == rhs.t ? id > rhs.id : t > rhs.t; }};priority_queue pq[MAXN], evt;void prelude() { for( int i = 1; i <= k; ++i ) { pq[x[i]].push( Node(0, i) ); SGT::add(x[i], 1); }}void run( ll t ) { while( !evt.empty() && evt.top().t <= t ) { Node car = evt.top(); evt.pop(); SGT::add(x[car.id], 1); // printf( "car.id = %d, x[id] = %d\n", car.id, x[car.id] ); pq[x[car.id]].push(car); }}int use( int pos ) { Node car = pq[pos].top(); pq[pos].pop(); SGT::add(pos, -1); return car.id;}int freecar( int pos ) { if( !SGT::sumv[1] ) return 0; int left = SGT::queryr(1, pos); int right = SGT::queryl(pos, n); // printf( "left = %d, right = %d\n", left, right ); if( !left ) left = -INF; if( !right ) right = INF; if( left == right ) { return use(left); } else if( pos-left < right-pos ) { return use(left); } else if( right-pos < pos-left ) { return use(right); } else { Node cl = pq[left].top(), cr = pq[right].top(); if( cl.t == cr.t ) { if( cl.id < cr.id ) { return use(left); } else { return use(right); } } else if( cl.t < cr.t ) { return use(left); } else { return use(right); } }}void solve() { ll now = 0; for( int i = 0; i < m; ++i ) { now = max(now, t[i]); run(now); int car = freecar( a[i] ); // printf( "now = %lld, car = %d\n", now, car ); if( !car ) { now = max(now, evt.top().t); run(now); // printf( "now = %lld, car = %d\n", now, car ); car = freecar( a[i] ); } // printf( "now = %lld, car = %d\n", now, car ); printf( "%d %lld\n", car, now - t[i] + abs(x[car] - a[i]) ); evt.push( Node(now + abs(x[car] - a[i]) + abs(a[i] - b[i]), car) ); x[car] = b[i]; }}int main() { _w = scanf( "%d%d%d", &n, &k, &m ); for( int i = 1; i <= k; ++i ) _w = scanf( "%d", x+i ); for( int i = 0; i < m; ++i ) _w = scanf( "%lld%d%d", t+i, a+i, b+i ); prelude(), solve(); return 0;}