游戏场地是一条由1 × n个方格单元组成的带状区域。一些单元格中有吃豆人，一些单元格中有星号，其他单元格为空。
吃豆人可以在1时间单位内移动到相邻的单元格。如果目标单元格中有星号，吃豆人会吃掉它。吃豆人吃星号不需要花费任何时间。
在初始时刻，所有吃豆人开始移动。每个吃豆人可以无限次改变移动方向，但不允许超出游戏场地的边界。吃豆人的移动不会干扰其他吃豆人的移动；在一个单元格中可以有任意数量的吃豆人以任意方向移动。
你的任务是确定吃豆人吃掉所有星号的最短可能时间。
输入
第一行包含一个整数n (2 ≤ n ≤ 105) — 游戏场地的长度。
第二行包含游戏场地的描述，由n个符号组成。如果在位置i中有符号'.' — 单元格i为空。如果在位置i中有符号'*' — 单元格i中包含星号。如果在位置i中有符号'P' — 吃豆人在单元格i中。
保证游戏场地上至少有一个吃豆人和至少一个星号。
输出
打印出吃豆人吃掉所有星号的最短可能时间。
注意
在第一个示例中，位置4的吃豆人将向左移动，并吃掉位置1的星号。他将花费3时间单位。在同样的3时间单位内，位置6的吃豆人将吃掉它相邻的两个星号。例如，它可以向左移动并吃掉位置5的星号（在1时间单位内），然后从位置5向右移动并吃掉位置7的星号（在2时间单位内）。因此，在3时间单位内，吃豆人将吃掉游戏场地上的所有星号。
在第二个示例中，位置4的吃豆人将向左移动，并在2时间单位后吃掉位置3和2的星号。位置5和8的吃豆人将向右移动，并在2时间单位内分别吃掉位置7和10的星号。因此，2时间单位足够吃豆人吃掉游戏场地上的所有星号。
分析：
首先题目让我们求的是最短的可能时间，那我们可以比较容易的联想到二分时间，再去验证该时间内吃豆人能不能把所有的豆都吃掉。
先给出一个样例：
*..P.P
我们贪心的考虑，最左侧的这个*肯定是由最左侧的P吃掉，不可能由右侧的那个P吃掉，那么贪心策略就很简单了：每次在二分出来的mid时间内，由最左侧的P吃掉最左侧*就可。
但是同时我们也需要考虑特殊情况，例如：
*..P.*
这样子P肯定是先吃一侧的再吃另一侧的，那么总时间是应该是先吃左侧的再吃右侧的这样花费时间最少。其实时间花费应该是两个*之间的间距+min(P和左侧*的间距,P和右侧*之间的间距).
那么思路就很明确了：利用优先队列(小根堆)每次只需要找出最左侧的*查看当前遍历到的P能否吃掉它，如果能吃掉就弹出堆，最后能全部吃完就返回true便可。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100;
priority_queue<int,vector<int>,greater<int>>q;
vector<int>res;
bool check(int x){
auto qq=q;
for(auto i:res){
if(qq.empty())break;
if(i-qq.top()>x)return false;
//当前遍历到的P不能在限定时间内吃到最左侧的*，那么后续的P都吃不到这个*了，所以我们直接返回false
int l=qq.top();
//记录最左侧的*的位置
while(!qq.empty()&&qq.top()<i)qq.pop();
//如果当前P能在限定时间内吃到这个*，那么就把它弹出堆
while(!qq.empty()&&qq.top()-l+min(abs(qq.top()-i),abs(i-l))<=x)qq.pop();
//当前P可以先吃一侧的再吃另一侧的
}
if(qq.empty())//吃完了
return true;
return false;
}
void solve(){
int n;
cin>>n;
string s;
cin>>s;
for(int i=1;i<=n;i++)
{
if(s[i-1]=='*')q.push(i);
else if(s[i-1]=='P')res.push_back(i);
}
ll l=1,r=1e9,ans=l;
while(l<=r){
int mid=l+r>>1;
if(check(mid)){
ans=mid,r=mid-1;
}
else l=mid+1;
}
cout<<ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--)
solve();
return 0;
}