Problem 2029 买票问题
Accept: 8 Submit: 56
Time Limit: 5000 mSec Memory Limit : 32768 KB
Problem Description
过年回家买票又排起了长队。刚开始队列为空的。 有四种情况： 1.队尾加进了一个编号为a，忍耐度为 b 的人，所有人的编号都不同。 2.队首的人买完票走了。 3.队列中忍耐度最低的人离开了队列。 4.在队伍变化的过程中，编号为x的人想知道他前面有多少人,如果人数大于 y 则他离开队伍。 所有人的编号和忍耐度都是一个整数(保证可以使用有符号32位整型保存)，且都是唯一的。
Input
输入数据包含多组测试数据输入数据第一行T表示操作的个数。(T <= 100000) 接着T行， add a b 表示队伍尾加入 编号a忍耐度b的人(a,b保证可以使用有符号32位整型保存) pop 队首的人买完票走了,如果队列为空则不执行此操作。 leave 队列中忍耐度最低的人离开了队列,如果队列为空则不执行此操作。 check x y在队伍变化的过程中，编号为x的人想知道他前面有多少人,如果人数大于 y 则他离开队伍,如果队列不含编号为x的人不执行此操作。(x,y保证可以使用有符号32位整型保存)
Output
对于第四种操作 输出编号为x的人前面的人数。
Sample Input
10
add 5 1
add 4 2
add 3 3
add 2 4
add 1 5
check 2 5
leave
check 2 1
pop
check 1 5
Sample Output
3
2
1
小根堆求最小值，树状数组求个数，map 求映射（注意加注释的几个erase，没有就超时，鄙视卡常数的！！！！）。
1
#include <iostream>
2#include <cstdio>
3#include <vector>
4#include <queue>
5#include <cstring>
6#include <map>
7
8using namespace std;
9
10const int T = 100009;
11
12struct Peo
13
{
14
Peo( int _a=0, int _b=0, int _q=0 ) : a(_a), b(_b), q(_q) {}
15
int a, b, q;
16
};
17
18class MinCmp
19{
20public :
21 bool operator()( const Peo &a, const Peo &b );
22};
23bool MinCmp::operator()( const Peo &a, const Peo &b ) {
24 return a.b > b.b;
25}
26
27int qh, qt, inq[ T ], sq[ T ], q2a[ T ];
28map< int, int > a2q;
29priority_queue< Peo, vector< Peo >, MinCmp > heap;
30
31#define lowbit(i) (i&((i-1)^i))
32
33void st_add( int i, int delta ) {
34 while ( i < T ) {
35 sq[ i ] += delta;
36 i += lowbit(i);
37
}
38}
39
40int st_sum( int i ) {
41 int s = 0;
42 while ( i > 0 ) {
43 s += sq[ i ];
44 i -= lowbit( i );
45 }
46 return s;
47}
48
49void init() {
50 while ( ! heap.empty() ) {
51 heap.pop();
52 }
53 qh = qt = 1;
54 a2q.clear();
55 memset( inq, 0, sizeof(inq) );
56 memset( sq, 0, sizeof(sq) );
57}
58
59void add( int a, int b ) {
60 a2q[ a ] = qt;
61 q2a[ qt ] = a;
62 heap.push( Peo( a, b, qt ) );
63 inq[ qt ] = 1;
64 st_add( qt, 1 );
65 ++qt;
66}
67
68void pop() {
69 while ( (qh<qt) && (inq[qh]==0) ) {
70 ++qh;
71 }
72 if ( qh < qt ) {
73 inq[ qh ] = 0;
74 a2q.erase( q2a[ qh ] );/**/////////////////////////////
75 st_add( qh, -1 );
76 ++qh;
77 }
78}
79
80void leave() {
81 Peo p;
82 while ( (!heap.empty()) && (inq[heap.top().q]==0) ) {
83 heap.pop();
84 }
85 if ( !heap.empty() ) {
86 p = heap.top();
87 inq[ p.q ] = 0;
88 st_add( p.q, -1 );
89 a2q.erase( q2a[ p.q ] );/**//////////////////////////////////
90 }
91}
92
93void check( int x, int y ) {
94 map< int, int >::iterator ite = a2q.find( x );
95 if ( ite != a2q.end() ) {
96 int q = ite->second;
97 int s = st_sum( q ) - 1;
98 printf( "%d\n", s );
99 if ( s > y ) {
100 inq[ q ] = 0;
101 st_add( q, -1 );
102 a2q.erase( ite );/**/////////////////////////////
103 }
104 }
105}
106
107int main() {
108 int t, a, b;
109 char cmd[ 100 ];
110 while ( scanf( "%d", &t ) == 1 ) {
111 init();
112 while ( t-- > 0 ) {
113 scanf( "%s", cmd );
114 if ( cmd[ 0 ] == 'a' ) {
115 scanf( "%d%d", &a, &b );
116 add( a, b );
117 }
118 else if ( cmd[ 0 ] == 'p' ) {
119 pop();
120 }
121 else if ( cmd[ 0 ] == 'l' ) {
122 leave();
123 }
124 else if ( cmd[ 0 ] == 'c' ) {
125 scanf( "%d%d", &a, &b );
126 check( a, b );
127 }
128 }
129 }
130 return 0;
131}
132