两种方法:直接模拟、线段树
由于编码菜,程序一大堆bug,下载测试数据,调试了两个钟头,才搞
太无语了。。。
1
#include <cstdio>
2
3
const int SIZE = 50001;
4
5
struct ROOM
6

{
7
int start;
8
int size;
9
struct ROOM *pre, *next;
10
}head, *tail, room[SIZE];
11
12
int N, M, gPos, gRSize;
13
14
void 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
25
void 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
41
void 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
92
int 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
115
int 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
}