題意是這樣的。
一個旅館有N個客房。
有兩種指令
1、分配長度為L的連續(xù)客房，盡量分配起始房間號小的
2、將[S,E]區(qū)間內(nèi)退房
對于第一種指令，我們需要在線段樹里維護(hù)3個域：lmax（與左端點相連的最長段）,rmax（與右端點相連的最長段）,max（總最長段）
轉(zhuǎn)移的時候如果左區(qū)間的lmax>need，則在左區(qū)間內(nèi)尋找；如果左區(qū)間的rmax+右區(qū)間的lmax>need，那么在左區(qū)間和右區(qū)間里共同分配，否則在右區(qū)間內(nèi)分配
還有一些細(xì)節(jié)，就不贅述了。
貼代碼
1
# include <cstdio>
2# include <cstring>
3# include <queue>
4# include <cstdlib>
5# include <vector>
6using namespace std;
7priority_queue<int,vector<int>,greater<int> > refer;
8struct node
9
{
10
int t,num;
11 char op;
12
};
13vector<node> data;
14int main()
15{
16 char str[100];
17 for(int i=1;i<=30000;i++)
18 refer.push(i);
19 int c[30001];
20 memset(c,0,sizeof(c));
21 while(gets(str))
22
{
23 node tmp;
24 tmp.t=atoi(strtok(str," "));
25 tmp.op=*strtok(NULL," ");
26 if(tmp.op=='.')
27 tmp.num=atoi(strtok(NULL," "));
28 data.push_back(tmp);
29
}
30 int now=0,last=0;
31 for(now=0;now<data.size();now++)
32 {
33 while(data[now].t-data[last].t>=600)
34 {
35 if(c[data[last].num]&&data[now].t-c[data[last].num]>=600)
36 {
37 refer.push(data[last].num);
38 c[data[last].num]=0;
39 }
40 last++;
41 }
42 switch(data[now].op)
43 {
44 case '+':
45 c[refer.top()]=data[now].t;
46 printf("%d\n",refer.top());
47 data[now].num=refer.top();
48 refer.pop();
49 break;
50 case '.':
51 if(c[data[now].num])
52 {
53 printf("+\n");
54 c[data[now].num]=data[now].t;
55 }
56 else
57 printf("-\n");
58 break;
59 };
60
61 }
62 //system("pause");
63 return 0;
64}
65
66