[SHOI2009]Booking 会场预约

题目：洛谷P2161。

题目大意：有一些操作，分为两种：

A.增加一个从第l天到第r天的预约，并删除与这个预约冲突的其他预约，输出删除了多少个预约。

B.输出当前有效预约个数。

两个预约冲突定义为两个预约有公共的日期。

解题思路：本题可以用STL巧妙解决。

首先要知道，STL中的lower_bound返回范围内第一个大于等于要查找的值的指针。

以下用区间来表示预约，[l,r]就表示第l天到第r天的预约。

首先建立结构体，l和r表示区间的左端点和右端点。

用set保存每个区间，比较方法为:按照r为第一关键字，小的在前，然后按照l为第二关键字，大的在前。

然后对于每个A操作，我们在set里用lower_bound查找[0,l]，返回的其实是原有区间中，右端点最小的，且大于等于当前区间左端点的一个区间。

然后比较一下查到的区间的左端点是否小于当前区间的右端点。

如果是，则删除这个区间，答案+1，并重复这个过程。

否则，因为查找到的区间严格大于当前区间（即没有冲突，且l和r都大于当前的l和r），那么下一个区间就严格大于查找到的区间，而当前区间的左端点大于上一个区间的右端点（或没有上一个区间），所以没有剩下的冲突了，结束查找，插入当前区间并输出答案。

对于B操作，只需输出set的size即可。

时间复杂度$O(n\log^2 n)$。

另外set自带lower_bound，范围默认为整个容器。

C++ Code：

#include<set>

#include<cstdio>

#include<algorithm>

#include<cctype>

using namespace std;

struct hy{

	int l,r;

	bool operator <(const hy&rhs)const{

		if(r!=rhs.r)return r<rhs.r;

		return l<rhs.l;

	}//以右端点为第一关键字，左端点为第二关键字

};

set<hy>s;

inline int readint(){

	char c=getchar();

	for(;!isdigit(c);c=getchar());

	int d=0;

	for(;isdigit(c);c=getchar())

	d=(d<<3)+(d<<1)+(c^'0');

	return d;

}

int main(){

	set<hy>::iterator it;

	for(int t=readint();t--;){

		char c=getchar();

		while(!isalpha(c))c=getchar();

		if(c=='A'){

			int l=readint(),r=readint(),ans=0;

			it=s.lower_bound((hy){0,l});

			while(it!=s.end()&&r>=it->l){

				++ans;

				s.erase(it);

				it=it=s.lower_bound((hy){0,l});

			}

			printf("%d\n",ans);

			s.insert((hy){l,r});

		}else printf("%u\n",s.size());

	}

	return 0;

}

好像在洛谷上跑了Rank1耶！

巴特西

[SHOI2009]Booking 会场预约

最新文章

热门文章