coreBugZJ

此 blog 已弃。

买票问题,福州大学第八届程序设计竞赛 之 D,FZU 2029

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=0int _b=0int _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< intint > 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, 0sizeof(inq) );
 56        memset( sq,  0sizeof(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< intint >::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

posted on 2011-04-30 23:34 coreBugZJ 阅读(438) 评论(1)  编辑 收藏 引用 所属分类: ACM

Feedback

# re: 买票问题,福州大学第八届程序设计竞赛 之 D,FZU 2029 2011-05-03 01:26 lijunle

这题可以用线段树做,代码量很大,但是需时会降低。

另外,我想问一下这场的《计数问题》怎么做?
http://acm.fzu.edu.cn/problem.php?pid=2031

如果方便,请通过邮件告诉我。谢谢。  回复  更多评论   



只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理