分析

最小化时间，可以考虑二分答案。

考虑将 Packmen 和物品的位置划分的成两个集合。由于 Packmen 之间互不影响，所以只要分别贪心就好了。

不难想到，每个人去走的物品一定是连续的。

对于一个位置为 \(p_i\) 的人 \(i\) 和一个物品区间 \([l,r]\)，能够在时间限制 \(x\) 内完成，当且仅当 \(\Big( \min(|p_i - l|,|p_i - r|) + |r-l| \Big) \le x\)。

维护 \(l\) 和 \(r\) 集合，check的复杂度是 \(O(n)\) 的。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e5+5;
int n;
char s[N];
vector<int> a, b;
bool can(int p,int l,int r,int t) {
	int d=min(abs(p-l),abs(p-r))+abs(r-l);
	return d<=t;
}
bool check(int x) {
	int l=0, r=0;
	for(int i=0;i<a.size();++i) {
		r=l;
		while(l<=r&&r<b.size()&&can(a[i],b[l],b[r],x)) ++r;
		l=r;
	}
	return l==b.size();
}
signed main() {
	n=read();
	scanf("%s",s);
	for(int i=0;i<n;++i) {
		if(s[i]=='*') b.push_back(i);
		else if(s[i]=='P') a.push_back(i);
	}
	int l=0, r=5*n;
	while(l<r) {
		int mid=(l+r)/2;
		if(check(mid)) r=mid; else l=mid+1;
	}
	printf("%lld\n",l);
}