97 lines
1.9 KiB
Java
97 lines
1.9 KiB
Java
package chelper;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.HashSet;
|
|
import java.util.List;
|
|
import java.util.Set;
|
|
import java.util.TreeSet;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class E extends SimpleSavingChelperSolution {
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
int n = in.nextInt();
|
|
String s = in.nextString();
|
|
|
|
TreeSet<Integer> pacmans = new TreeSet<>();
|
|
TreeSet<Integer> allStars = new TreeSet<>();
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
char c = s.charAt(i);
|
|
|
|
if (c == 'P') {
|
|
pacmans.add(i);
|
|
}
|
|
|
|
if (c == '*') {
|
|
allStars.add(i);
|
|
}
|
|
}
|
|
|
|
int l = -1;
|
|
int r = n * 10;
|
|
|
|
while (r - l > 1) {
|
|
int m = (l + r) / 2;
|
|
|
|
TreeSet<Integer> stars = new TreeSet<>(allStars);
|
|
|
|
for (Integer pacman : pacmans) {
|
|
int L = pacman;
|
|
int R = pacman;
|
|
|
|
while (!stars.isEmpty()) {
|
|
int k = stars.first();
|
|
|
|
int L1 = Math.min(L, k);
|
|
int R1 = Math.max(R, k);
|
|
|
|
int dist = Math.min(pacman - L1, R1 - pacman) + R1 - L1;
|
|
if (dist <= m) {
|
|
stars.pollFirst();
|
|
L = L1;
|
|
R = R1;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
|
|
|
|
// while (left > 0 && !stars.isEmpty()) {
|
|
// int k = stars.first();
|
|
//
|
|
// int dist = Math.abs(pos - k);
|
|
//
|
|
// if (dist <= left) {
|
|
// stars.removeAll(new TreeSet<>(stars.subSet(
|
|
// Math.min(k, pos),
|
|
// Math.max(k, pos) + 1)));
|
|
//
|
|
// left -= dist;
|
|
// pos = k;
|
|
// } else {
|
|
// break;
|
|
// }
|
|
// }
|
|
}
|
|
|
|
if (stars.isEmpty()) {
|
|
r = m;
|
|
} else {
|
|
l = m;
|
|
}
|
|
}
|
|
|
|
out.println(r);
|
|
}
|
|
}
|