PREREQUISITES:
Binary Search, Two-Pointers
PROBLEM Statement:
Now there is a road with a size of 1*n, which is composed of dots.‘.’ means that the spot is empty, ‘l’ means that there is letter at this spot, and ‘p’ means that there is a postman at this spot, and each postman can go in any direction Walk, it takes 1 unit of time to walk one grid, ensure that there is at least one postman, at least one letter, and ask for the minimum time to collect all the letter (the point when a postman walks to the letter means that the letter is taken and taking a letter does not take time).
Your task is to determine minimum possible time after which Postman can collect all the letter(l).
Approach:
Knowing the total length n of the road, we can know that the answer must fall within the interval of [1, 2n] (in fact, the answer must be less than 1.5n. For the sake of insurance, the maximum is 2n). So we can divide the answer in this interval. If we know the answer, we can judge whether postman can collect up all the letter under this answer. If we can, we can divide the answer into a smaller range ([l, mid-1]), on the contrary, go to the range of greater value by half ([mid+1,r]).
How to judge whether a postman can finish collecting letter in this time according to the currently known time m:
Traverse the road from left to right:
1.If you first traverse to a point as ‘l’ and there is no ‘p’ in front, then save the position of this point. If there is a ‘l’ in front of this, you don’t need to save it, as long as you save the smallest ‘l’, it will be OK Up.
2.If traversing to a point is ‘p’, set the position as i:
a. If there is no letter ‘l’ in front of ‘p’, then there is no need to consider the road to i+m, because it will definitely be taken by this ‘p’. Of course, pay attention to it. If there is still a point on the road as ‘p’, then Start with this ‘p’ instead of i+m, because this ‘p’ can definitely go farther, and if you start directly from i+m, this will be ignored, which will cause losses (not the optimal way) .
b. If there is letter ‘l’ in front of ‘p’, and if ‘p’ cannot reach the point of the letter in front of it within m, then m must be too small, that is, it is impossible to collect all the letter within m. If you can, then two situations should be considered:
If m>=3*x (x represents the distance from the current ‘p’ to the letter that has not been taken), then it must go forward and take that one and come back.
If m<3*x, then walking backward and then going back is just good to take that, so as to ensure that you can walk as much distance as possible.
Assuming that you can reach the point as far as tmp ,Then there is no need to consider the road to tmp, because it will definitely be taken by this ‘p’. Of course, we should also pay attention to it. If there is still a little ‘p’ on this road, then start with this ‘p’.
This is the optimal move.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
const int MAX = 1e5 + 100;
int n;
char str[MAX];
bool judge(int m)
{
int pos1=-1;//The position of the letter that has not been taken
for(int i=0;i<n;i++)
{
if(str[i]=='*')
{
if(pos1==-1)
pos1=i;
}
if(str[i]=='p')
{
//There is no untaken letter before
if(pos1==-1)
{
pos1=-1;
int j;
for(j=i+1;j<=i+m;j++)
{
if(str[j]=='p')
{
break;
}
}
i=j-1;
}
//There is still untaken letter ahead
else
{
if(i-pos1>m)
return false;
int tmp;
if(m>=3*(i-pos1))
{
tmp=pos1+m-(i-pos1);
tmp=max(tmp,i);
}
else
{
tmp=i+(m-(i-pos1))/2;
}
pos1=-1;
if(tmp>i)
{
int j;
for(j=i+1;j<=tmp;j++)
{
if(str[j]=='p')
{
break;
}
}
i=j-1;
}
else
i=tmp;
continue;
}
}
}
if(pos1!=-1)
return false;
return true;
}
int main()
{
scanf("%d",&n);
scanf("%s",str);
int len=strlen(str);
int l=1,r=2*n;
int ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(judge(mid)==true)
{
r=mid-1;
ans=mid;
}
else
{
l=mid+1;
}
}
printf("%d\n",ans);
return 0;
}