E. Packmen(贪心+二分[注意细节])

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

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

$或者向右走再向左走$

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

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

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

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

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

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

#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; #define f first #define s second typedef pair<int,int>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<<ans; }

另一份贪心+二分

$思路来源于$点我呀

#include <bits/stdc++.h> 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<mid )//先左边再右边可以往右走得更远 last=i+mid-2*x; else //先右边再左边 last=(mid-x)/2+i; } pos=-1; } } if(pos==-1) return true; return false; } int main() { cin >> 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<<ans; }