gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
两种方法:直接模拟、线段树
由于编码菜,程序一大堆bug,下载测试数据,调试了两个钟头,才搞
太无语了。。。
  1#include <cstdio>
  2
  3const int SIZE = 50001;
  4
  5struct ROOM
  6{
  7    int start;
  8    int size;
  9    struct ROOM *pre, *next;
 10}
head, *tail, room[SIZE];
 11
 12int N, M, gPos, gRSize;
 13
 14void Init()
 15{
 16    gPos = gRSize = 1;
 17    head.next = &room[0];
 18    tail = &room[0];
 19    room[0].start = 1;
 20    room[0].size = N;
 21    room[0].pre = &head;
 22    room[0].next = NULL;
 23}

 24
 25void Del(ROOM *ptr, const int& size)
 26{
 27    if ( ptr->size == size )
 28    {
 29        ptr->pre->next = ptr->next;
 30        if( ptr->next )
 31            ptr->next->pre = ptr->pre;
 32        else
 33            tail = ptr->pre;
 34    }

 35    else {
 36        ptr->size = ptr->size - size;
 37        ptr->start = ptr->start + size;
 38    }

 39}

 40
 41void Add(const int& st, const int& size)
 42{
 43    int end = st + size ;
 44    ROOM *ptr = head.next;
 45
 46    tail->next = &room[gPos];
 47    room[gPos].pre = tail;
 48    room[gPos].start = st;
 49    room[gPos].size = size;
 50    room[gPos].next = NULL;
 51    tail = &room[gPos];
 52    gPos++;
 53
 54    while ( ptr && ptr != tail)
 55    {
 56        if ( (ptr->start + ptr->size) == tail->start )
 57        {
 58            tail->start = ptr->start;
 59            tail->size += ptr->size;
 60            Del( ptr, ptr->size );
 61        }

 62        else if ( ptr->start == end )
 63        {
 64            tail->size += ptr->size;
 65            Del( ptr, ptr->size );
 66        }

 67        else if ( ptr->start >= tail->start && (ptr->start + ptr->size) <= (tail->start + tail->size) )
 68            Del( ptr, ptr->size );
 69        else if ( ptr->start >= tail->start && ptr->start < (tail->start + tail->size) )
 70        {
 71            tail->size += (ptr->start + ptr->size - tail->start - tail->size);
 72            Del( ptr, ptr->size );
 73        }

 74        else if ( ptr->start <= tail->start && (ptr->start + ptr->size) >= (tail->start + tail->size) )
 75        {
 76            tail->start = ptr->start;
 77            tail->size = ptr->size;
 78            Del( ptr, ptr->size );
 79            break;
 80        }

 81        else if ( ptr->start <= tail->start && (ptr->start + ptr->size) > tail->start )
 82        {
 83            tail->size += (tail->start - ptr->start);
 84            tail->start = ptr->start;    
 85            Del( ptr, ptr->size );
 86        }

 87        ptr = ptr->next;
 88    }

 89
 90}

 91
 92int Find(const int& size)
 93{
 94    int st = 0;
 95    ROOM *= head.next, *tmp;
 96
 97    while ( p )
 98    {
 99        if ( p->size >= size && (st == 0 || st > p->start) )
100        {
101            st = p->start;
102            tmp = p;
103        }

104        p = p->next;
105    }

106
107    if ( st == 0 )
108        return 0;
109
110    Del(tmp, size);
111
112    return st;
113}

114
115int main()
116{
117//    freopen("1.txt", "r", stdin);
118
119    int i, num, s, d;
120
121    scanf("%d %d"&N, &M);
122
123    Init();
124
125    for ( i = 0; i < M; ++i )
126    {
127        scanf("%d"&num);
128
129        if ( num == 1 )
130        {
131            scanf("%d"&s);
132            printf("%d\n", Find(s));
133
134        }

135        else {
136            scanf("%d %d"&s, &d);
137            Add( s, d );
138        }

139    }

140    return 0;
141}
posted on 2009-03-22 15:58 阅读(333) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理