abc333 E求调
查看原帖
abc333 E求调
865625
KobeBeanBryantCox楼主2023/12/16 22:19

思路:对于每个怪物,往前找 相应的、没用过的、距离当前怪物最近的 药水,捡起来(相当于倒着来)

代码中的 x 数组存药水,f 数组是捡不捡这个药水,num 和 nex 是链表,方便找到每个怪物的 相应的、没用过的、距离当前怪物最近的 药水

时间复杂度 O(n)O(n),但是不知道为啥莫名 WA

记录

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
int in()
{
	int k=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
void out(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x<10)putchar(x+'0');
	else out(x/10),putchar(x%10+'0');
}
const int N=2e5+10;
int a[N];
int x[N],len=0;
bool f[N];
int num[N],nex[N];
int main()
{
	int n=in();
	for(int i=1;i<=n;i++)
	{
		a[i]=in();
		int xx=in();
		if(a[i]==1)x[++len]=xx,nex[len]=num[xx],num[xx]=len;
		else
		{
			if(num[xx]==0)out(-1),exit(0);
			f[num[xx]]=true;
			num[xx]=nex[num[xx]];
		}
	}
	int ans=0,sum=0,u=0;
	for(int i=1;i<=n;i++)
		if(a[i]==2)ans=max(ans,sum),sum=0;
		else if(f[++u])sum++;
	out(ans),putchar('\n');
	for(int i=1;i<=len;i++)cout<<f[i]<<" ";
	return 0;
}
2023/12/16 22:19
加载中...