出题人题解 | #Rabbit的机器人#

原题解链接：https://ac.nowcoder.com/discuss/151166

二分

首先我们明确一点,如果要放障碍物$00$号方格左右最多放一个，因为只要碰到一个就不会继续走过去了，也就是说放置多个障碍物只有最靠近0号方格的是有意义的。

此外因为要保证最后一次到达没到过的地方，不可能两侧都放，因为这样的话要不就是不满足题意，要不就是其中一个障碍没有意义，所以障碍物的上限是$11$个。

然后如果最后一个指令为$L\mathrm{/}RL/R$,那么障碍物要放一定放在$00$号方格右侧/左侧。且以障碍物放在$00$号方格右侧为例，如果障碍物放在$xx$处满足题意的话，放在$x-1x-1$这个位置也是满足题意的(最后向左能走得更远)。

据此我们只要去查找障碍物可以摆放的最右位置,满足单调性质，用二分查找即可。

#include <cstdio>
#include <bits/stdc++.h>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)

typedef long long ll;
const int maxn = 1000005;
const ll INF = 1e18;
const ll mod=1e9+7;
const double eps = 1e-7;

char s[maxn];
char tmp;
int len;

int check(int x)
{
    int pos=0;
    int Max=0;
    for(int i=0;i<len;i++)
    {
        Max=max(Max,pos);
        if(s[i]==tmp) pos++;
        else pos--;
        if(pos==-x) pos++;
    }
    return pos>Max;
}

int main()
{
    int len1;
    scanf("%d",&len1);
    scanf("%s",s);
    len=strlen(s);
    tmp=s[len-1];
    int l=1,r=len;
    int ans=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    if(ans==-1) puts("-1");
    else if(ans==len) puts("0 1");
    else printf("1 %d\n",ans);
}