CodeForces 219E Parking Lot

　　原题链接：http://codeforces.com/problemset/problem/219/E

　　这题和hotel那题很像，一开始想到的是用线段树，设0为空位，1为占位，那么需要维护左端最长0，右端最长0，中间最长0，然后在插入删除操作中需要考虑区间的合并，区间的分解等问题……瞬间就被恶心到了。

　　网上看到别人一种奇妙的做法，运用STL里面的set容器进行一个模拟线段树而又类似贪心的做法，代码量大大减少了，写起来非常方便。用了set容器，那么这道题就是纯粹的对set进行增加删除元素了。

View Code

 1 /*
 2     代码出处：http://www.cnblogs.com/Delostik/archive/2012/08/28/2660073.html
 3     排序，贪心
 4 */
 5 #include <iostream>
 6 #include <cstdio>
 7 #include <cstdlib>
 8 #include <cstring>
 9 #include <queue>
10 #include <vector>
11 #include <utility>
12 #include <cmath>
13 #include <string>
14 #include <map>
15 #include <set>
16 #define inf 2147483647
17 using namespace std;
18 template<class T>inline void gmax(T &a,T b)
19 {if(a<b)a=b;}
20 template<class T>inline void gmin(T &a,T b)
21 {if(a>b)a=b;}
22 typedef pair<int,int> PII;
23 typedef long long LL;
24 
25 int n,m,sym,id,lot[1000010],L[200010],R[200010];
26 
27 struct SEGMENT
28 {
29     int len,st,pos;
30 } cur;
31 
32 struct cmp
33 {
34     bool operator()(const SEGMENT a,SEGMENT b)
35     {
36         if(a.len==b.len) return a.pos<b.pos;
37         else return a.len>b.len;
38     }
39 };
40 
41 set<SEGMENT,cmp> seg;
42 
43 SEGMENT Make_seg(int left,int right)
44 {
45     SEGMENT res;
46     if(!left && right==n+1) res.len=inf,res.st=0,res.pos=1;
47     else if(!left) res.len=right-1,res.st=0,res.pos=1;
48     else if(right==n+1) res.len=n-left,res.st=left,res.pos=n;
49     else res.len=(right-left)>>1,res.st=left,res.pos=left+res.len;
50     return res;
51 }
52 
53 void Insert_seg(int left,int right)
54 {
55     L[right]=left,R[left]=right;
56     seg.insert(Make_seg(left,right));
57 }
58 
59 void Del_seg(int left,int right)
60 {seg.erase(Make_seg(left,right));}
61 
62 int main()
63 {
64     cin>>n>>m;
65     Insert_seg(0,n+1);
66     while(m--)
67     {
68         cin>>sym>>id;
69         if(sym==1)
70         {
71             cur=*seg.begin();
72             seg.erase(seg.begin());
73             lot[id]=cur.pos;
74             int pnt1=cur.st,pnt2=cur.pos,pnt3=R[pnt1];
75             Insert_seg(pnt1,pnt2);
76             Insert_seg(pnt2,pnt3);
77             cout<<lot[id]<<endl;
78         }
79         else
80         {
81             int pnt1=L[lot[id]],pnt2=lot[id],pnt3=R[pnt2];
82             Del_seg(pnt1,pnt2);
83             Del_seg(pnt2,pnt3);
84             Insert_seg(pnt1,pnt3);
85         }
86     }
87 }