本文共 2137 字，大约阅读时间需要 7 分钟。

这题虽然想到了贪心+二分,但是模拟细节wa到怀疑人生…

$因为考虑每个p有两种走法,向左走再向右走$

$或者向右走再向左走$

$那么我们先考虑第一个p$

$这个p左边的所有\ast 都被吃掉,设走到最左边的\ast 距离是l$

$然后右边也会有部分\ast 被吃掉,设走到最右边的\ast 是r$

$所以就是需要走min(l,r)\ast 2+max(l,r)$

$然后记录一下这个p走到最右边的点r$

$下一个p需要把r到自己间的\ast 都吃掉$

#include 
   
    using namespace std;const int maxn=2e5+10;#define f first#define s secondtypedef pair
    
     p;int n,top,Left,in[maxn],sumn;char a[maxn];bool isok(int mid){	int l=Left,temp=0;//l表示当前没有被吃掉的最左边的* 	for(int i=1;i<=top;i++)	{		int index=in[i],q=in[i];//当前p的位置是index 		for(int j=index-1;j>=l;j--)//首先把[l,index-1]所有*吃掉 		{			if(a[j]!='*')	continue;			if(index-j>mid)	return false;			q=j,temp++;//消掉星星			}		l=index+1;		for(int j=index+1;j<=n;j++)//现在就尽可能多吃[index+1,n]的* 		{			if(a[j]=='P')	break;//留给下一个p去处理吧,下一个p吃的更远 			if(a[j]=='.')	continue;			int now=j-index;//假设这个now是吃掉的最右边的点 			if(min(now,index-q)*2+max(now,index-q)<=mid)				temp++,l=j+1;			else	break;			} 	}	if(temp==sumn)	return true;	else	return false;}int main(){	cin >> n >> (a+1);	for(int i=1;i<=n;i++)	{		if(a[i]=='*')		{			sumn++;			if(Left==0)	Left=i;		}		else if(a[i]=='P')	in[++top]=i;	}	int l=1,r=n*2,mid,ans;	while(r>=l)	{		mid =l+r>>1;		if( isok(mid) )	r=mid-1,ans=mid;			else	l=mid+1;	}	cout<
    
   

另一份贪心+二分

$思路来源于$

#include 
   
    using namespace std;int n;char s[200009];bool isok(int mid){	int pos=-1,last=-1;//pos记录*的位置,last是当前覆盖到的最远点 	for(int i=1;i<=n;i++)	{		if(i>last&&s[i]=='*'&&pos==-1)	pos=i;//遇到没有标记的*		if(s[i]=='P')		{			if(pos==-1)//前面没有*,直接往右走 				last=i+mid;				else			{				int x = i-pos;//求出去左边的距离				if( x>mid )	return false;//到不了				if( x*3
    
     > n >> (s+1);	int l=1,r=n*2,ans=-1;	while(r>=l)	{		int mid = (l+r)/2;		if( isok(mid) )	r=mid-1,ans=mid;		else	l=mid+1;	}	cout<
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/107129264 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！