题目大意
有一个长为L的街道可用来停车，司机在寻找停车位的时候，要求与后车的车距不少于b,与前车的距离不少于f。总共有两种操作，第一种操作是查询是否有可以停车的空位，如果有多个空位可以选择的话，选择最靠左的空位停车，并返回它的左端位置。第二种操作是让第x次操作的车从所占的车位开走。
题解
和POJ3677Hotel差不多，都是寻找连续的空位。不过要注意第一辆车是不需要考虑前方车距的，最后一辆车不需要后方车距。我们可以把街道长度扩充为L+ b+f即可，假设车长为x，那么每次查询长度大于等于x+b+f的空位就OK了。
代码：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define lson l,m,s<<1 #define rson m+1,r,s<<1|1 #define MAXN 110000 typedef struct { int l; int r; } NODE; int msum[MAXN<<2],rsum[MAXN<<2],lsum[MAXN<<2],setv[MAXN<<2]; NODE t[MAXN]; void PushUp(int s,int m) { msum[s]=max(max(msum[s<<1],msum[s<<1|1]),rsum[s<<1]+lsum[s<<1|1]); lsum[s]=lsum[s<<1]; rsum[s]=rsum[s<<1|1]; if(lsum[s<<1]==(m-(m>>1))) lsum[s]+=lsum[s<<1|1]; if(rsum[s<<1|1]==(m>>1)) rsum[s]+=rsum[s<<1]; } void PushDown(int s,int m) { if(setv[s]!=-1) { setv[s<<1]=setv[s<<1|1]=setv[s]; lsum[s<<1]=rsum[s<<1]=msum[s<<1]=setv[s]*(m-(m>>1)); lsum[s<<1|1]=rsum[s<<1|1]=msum[s<<1|1]=setv[s]*(m>>1); setv[s]=-1; } } void build(int l,int r,int s) { setv[s]=-1; msum[s]=lsum[s]=rsum[s]=r-l+1; if(l==r) return; int m=(l+r)>>1; build(lson); build(rson); } void update(int ql,int qr,int d,int l,int r,int s) { if(ql<=l&&r<=qr) { setv[s]=d; msum[s]=lsum[s]=rsum[s]=d*(r-l+1); return; } PushDown(s,r-l+1); int m=(l+r)>>1; if(ql<=m) update(ql,qr,d,lson); if(qr>m) update(ql,qr,d,rson); PushUp(s,r-l+1); } int query(int w,int l,int r,int s ) { if(l==r) return l; PushDown(s,r-l+1); int m=(l+r)>>1; if(msum[s<<1]>=w) return query(w,lson); else if(rsum[s<<1]+lsum[s<<1|1]>=w) return m-rsum[s<<1]+1; else return query(w,rson); } int main(void) { int l,b,f,a,x,pos,m,p=0; while(scanf("%d%d%d",&l,&b,&f)!=EOF) { l=l+b+f-1; build(0,l,1); scanf("%d",&m); while(m--) { ++p; scanf("%d%d",&a,&x); if(a==1) { if(msum[1]<x+b+f) printf("-1\n"); else { pos=query(x+b+f,0,l,1); printf("%d\n",pos); t[p].l=pos+b; t[p].r=pos+x+b-1; update(t[p].l,t[p].r,0,0,l,1); } } else update(t[x].l,t[x].r,1,0,l,1); } } return 0; }
再贴上大神的代码以供膜拜。。。容器果然是个好东西。。。。
#include <cstdio> #include <vector> #include <utility> #include <algorithm> using namespace std; const int INF = 1000000000; int main() { int L, B, F, n, a[128], b[128]; pair<int, int> p[128]; vector<pair<int, int> > v; scanf("%d%d%d", &L, &F, &B); v.push_back(make_pair(-INF, -F)); v.push_back(make_pair(L + B, INF)); scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d%d", &a[i], &b[i]); if (a[i] == 2) { v.erase(find(v.begin(), v.end(), p[b[i]])); } else { p[i].first = -1; for (int j = 1; j < (int)v.size(); ++j) { if (v[j - 1].second + F + b[i] + B <= v[j].first) { p[i] = make_pair(v[j - 1].second + F, v[j - 1].second + F + b[i]); v.push_back(p[i]); sort(v.begin(), v.end()); break; } } printf("%d\n", p[i].first); } } return 0; }