Packmen

大意：
$1\ast n$的地图有豆子和人，每个豆子每一秒可以往左或右移动一个单位长度，吃豆子不消耗时间，最短吃完所有豆子的时间

分析:
$n\le 10^5$大概率只能用$O(nlogn)$的算法，自然地可以猜测是二分答案+验证的套路,问题是验证怎么验证，我们先记录每个豆子右边最近的人在什么位置,然后从左往右记录能移动的最大位置,对于豆子看是否可以有人在二分的时间内过来,有两种情况，一种是先向向左到豆子再尽量往右走，第二种是先向右走再向左走，取向右走位置，二者取max
如果先遇到的是人直接向右走即可（因为是从左往右遍历的）

#include<bits/stdc++.h>
using namespace std;

int n;
string s,ss;
int minn[1010100];

bool check(int x){
    int maxw=0;
    ss = s;
    for (int i=1;i<=n;i++){
        if (ss[i] == '.') continue;
        if (ss[i] == 'P') {maxw = max(maxw,i+x);continue;}
        if (ss[i] == '*'){
            if (i<=maxw) continue;
            int d = minn[i] - i;
            if (d<0 || d>x) return 0;
            maxw = max({maxw,minn[i]+x-d-d,minn[i]+(x-d)/2});
            ss[minn[i]] = '.';
        }
    }
    return 1;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>s;
    s = ' '+s;

    for(int i = n,post = 0;i>=1;--i){
        if(s[i]=='P') post = i;
        if(s[i]=='*') minn[i] = post;
    }
    int l=0,r=1e9;
    while(l<=r){
        int mid = (l+r)>>1;
        if(check(mid)) r = mid-1;
        else l = mid+1;
    }
    cout<<l;
    return 0;
}