自动搬运

查看原文

来自洛谷，原作者为

	Zvelig1205 Q:3044754855 欢迎来吊打我

搬运于2025-08-24 21:44:59，当前版本为作者最后更新于2022-08-14 19:58:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P3071 [USACO13JAN]Seating G

前言 闲话

哎，P2894 珂朵莉被卡了

推荐题目……

！有一个没做过

于是

题目传送门

思路

那当然珂朵莉了

对于“离开”操作，直接区间推平为 0。

而对于“安置”操作，直接暴力扫一遍珂树，找到足够大的空区间就将客人安置到那里，即区间推平为 1。

找空位的时候，可能出现两个相邻的区间都为 0 的情况（对珂树足够了解的人应该能看懂这句话），所以统计答案时不能只看当前区间，也要注意和之前的区间的关系：

• 当前区间为空：

  • 若前一个区间为空，则直接将区间长度累加到待选空区间长度 $sum$ 中；

  • 若前一个区间不空，则将当前区间的左端点记录为整个待选空区间的左端点 $L$。

• 当前区间不空：

  清空 $sum$ 和 $L$。

• 找到合适的空区间：

  返回空区间左端点。若遍历整个珂树都没有满足条件的 $sum$，返回 -1（即无解）

贴一下代码

int n,m,l,r,ans;
struct C_Tree{
	int le,ri,val;
	C_Tree(int le,int ri=0,int val=0):
		le(le),ri(ri),val(val){}
	bool operator <(const C_Tree &b)const
	{
		return le<b.le;
	}
};
set<C_Tree>T;
#define IT set<C_Tree>::iterator
IT split(int now)
{
	IT i=T.lower_bound(C_Tree(now));
	if(i!=T.end()&&i->le==now)return i;
	i--;int l=i->le,r=i->ri,v=i->val;
	T.erase(i);
	T.insert(C_Tree(l,now-1,v));
	return T.insert(C_Tree(now,r,v)).first;
}
void assign(int l,int r,int k)
{
	IT ir=split(r+1),il=split(l);
	T.erase(il,ir);
	T.insert(C_Tree(l,r,k));
}
int ask(int siz)
{
	int sum=0,pos=0;
	for(IT i=T.begin();i!=T.end();i++)
	{
		if(i->val==0)
		{
			if(pos==0)pos=i->le;
			sum+=i->ri-i->le+1;
			if(sum>=siz)return pos;
		}
		else sum=pos=0;
	}
	return -1;
}
signed main()
{
	n=re();m=re();
	T.insert(C_Tree(1,n,0));
	for(int i=1;i<=m;i++)
	{
		char op[10]="";scanf("%s",op);
		if(op[0]=='A')
		{
			l=re(),r=ask(l);
			if(r!=-1)assign(r,r+l-1,1);
			else ans++;
		}
		else l=re(),r=re(),assign(l,r,0);
	}
	wr(ans);
	return 0;
}

一点小坑

$sum$ 是否满足的条件应该是 $\ge siz$ 而不是 $>siz$，不然就会取得 50 分的好成绩。

应该没人会和我一样犯这么傻的错误

后记

话说这题的标签……

为什么是 队列、单调队列、离散化？

广告

珂朵莉树教程

我的 Blog