兩種方法：直接模擬、線段樹
由于編碼菜，程序一大堆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 *p = 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}