bzoj1593[Usaco2008 Feb]Hotel旅馆

本文主要是介绍bzoj1593[Usaco2008 Feb]Hotel旅馆，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1593

题目大意：

有一家著名旅馆，这家旅馆一共有N 间客房，都在同一楼层，一字顺序排开。旅店前台的工作是忙碌的，他们需要处理订房请求和退房请求。有订房请求的游客会要求预定一
段连续的房间。如果能够满足客户的要求，前台总会尽量满足，如果有多处连续的空房可供预定，前台会挑选编号最靠前的优先分配。如果目前没有连续的空房，前台会向他们道歉，请顾客们另找一家宾馆。同时，前台也会收到退房请求，请求退房时，客户会报出一组连续的区间，前台将这片区域标记成空房。有时，在客户报出的区间中，有些房间本来就是空的，这不要紧，只需要把不是空房的房间全部登记成空房就可以了。
你的工作，就是写一个程序，帮助前台为旅客安排房间。程序一共需要处理M 条请求，在第一个请求之前，所有房间都是空闲的。

题解：

线段树区间修改

我的代码可能很,,维护了四个值cz,cy,c,sm和一个lazy标记la

cz表示这个区间里从左边开始最多有多少连续的空房，cy就是从右边开始...，c就是标记一下这一整个区间是不是空的，不是的话为-1，sm表示这个区间里最多有多少间连续的空房。为什么有sm呢?因为空房有可能在中间连续而cz,cy是记录不到的，又要编号靠前的优先，所以存个sm。

修改的话就区间修改啊，记得lazy的更新。

询问就从树根开始往下走。每次都优先考虑左边就好了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 101000struct node
{int l,r,lc,rc,cz,cy,c,sm,la;
}tr[maxn];int len;
int mymax(int x,int y){return (x>y)?x:y;}
void bt(int l,int r)
{len++;int now=len;tr[now].l=l;tr[now].r=r;tr[now].lc=tr[now].rc=-1;tr[now].cz=tr[now].cy=tr[now].sm=r-l+1;tr[now].c=0;tr[now].la=-1;if (l<r){int mid=(l+r)>>1;tr[now].lc=len+1;bt(l,mid);tr[now].rc=len+1;bt(mid+1,r);}
}
void down(int now,int lc,int rc)
{if (tr[now].la==1){tr[lc].cy=tr[lc].cz=tr[lc].sm=0;tr[rc].cy=tr[rc].cz=tr[rc].sm=0;}else{tr[lc].cy=tr[lc].cz=tr[lc].sm=tr[lc].r-tr[lc].l+1;tr[rc].cy=tr[rc].cz=tr[rc].sm=tr[rc].r-tr[rc].l+1;}tr[lc].c=tr[rc].c=tr[now].c;tr[lc].la=tr[rc].la=tr[now].la;tr[now].la=-1;
}
void updata(int now,int lc,int rc)
{if (tr[lc].c==tr[rc].c) tr[now].c=tr[lc].c;else tr[now].c=-1;tr[now].cz=tr[lc].cz;tr[now].cy=tr[rc].cy;if (tr[lc].c==0) tr[now].cz+=tr[rc].cz;if (tr[rc].c==0) tr[now].cy+=tr[lc].cy;tr[now].sm=mymax(tr[lc].sm,mymax(tr[rc].sm,tr[lc].cy+tr[rc].cz));
}
void change(int now,int l,int r,int k)
{if (tr[now].l==l && tr[now].r==r){if (k==1) tr[now].cy=tr[now].cz=tr[now].sm=0;else tr[now].cy=tr[now].cz=tr[now].sm=r-l+1;tr[now].c=tr[now].la=k;return;}int mid=(tr[now].l+tr[now].r)>>1,lc=tr[now].lc,rc=tr[now].rc;if (tr[now].la!=-1) down(now,lc,rc);if (r<=mid) change(lc,l,r,k);else if (l>mid) change(rc,l,r,k);else change(lc,l,mid,k),change(rc,mid+1,r,k);updata(now,lc,rc);
}
int query(int now,int k)
{int ret=-1;while (1){if (now==-1) break;if (tr[now].sm<k) break;//没有满足条件的直接breakif (tr[now].cz>=k) {ret=tr[now].l;break;}//左边满足直接返回左端点int lc=tr[now].lc,rc=tr[now].rc;if (tr[lc].sm>=k) now=lc;//左边有满足的去左边else//如果左边没有满足的但整个区间有满足的要么在中间要么在右边{if (tr[lc].cy!=0 && tr[lc].cy+tr[rc].cz>=k) {ret=tr[lc].r-tr[lc].cy+1;break;}//中间满足的话直接返回在左孩子的起始位置else now=rc;//在右边的}}return ret;
}
int main()
{//freopen("hotel.in","r",stdin);//freopen("hotel.out","w",stdout);int n,m,i,x,t,k,ans;scanf("%d%d",&n,&m);len=0;bt(1,n);for (i=1;i<=m;i++){scanf("%d",&t);if (t==1){scanf("%d",&x);ans=query(1,x);//返回能提供空房的起始位置if (ans!=-1){printf("%d\n",ans);change(1,ans,ans+x-1,1);//改成有人}else printf("0\n");}else if (t==2){scanf("%d%d",&x,&k);change(1,x,x+k-1,0);//退房操作->空房
}}return 0;
}

这篇关于bzoj1593[Usaco2008 Feb]Hotel旅馆的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---