本文主要是介绍CodeForces 404E Maze 1D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
一个机器人在数轴上的0点 给一串指令机器人按照指令走 为了使机器人最后一步走到一个从来没来过的位置 我们可以在数轴上放石头 每次机器人被石头卡住他就跳过当前的那个指令 问 最少使用石头前提下 一共几种放石头方法
思路：
很容易想到如果最后一个指令是L 那么机器人一定会停在0点的左边 因为如果停在右边 最后一步一定走在之前来过的位置上 同理最后一个指令是R
而且 放石头只有两种方案 放一个或不放！ 因为放两个一定有一个石头没用
所以一开始先按没石头的方案走一遍 如果满足条件 那么就不用放石头输出答案1就好（因为保证放石头数最少）
如果不放石头不行 那么就要分类讨论 是放左边还是放右边
根据最后一个指令判断 如果是L 则一定停在0点左边 所以石头放右边 同理是R
这时可以二分放石头的位置来确定answer
因为 如果石头放在右边 3的位置上放石头满足条件 1、2位置一定也满足
理由就是1、2放石头一定可以使最后停下的位置比3放石头最后停下的位置还往左
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define M 1001000char str[M];
int vis[M*2];
__int64 ans;
int n,fl,fr;bool yes(int stone)
{int i,j;memset(vis,0,sizeof(vis));for(i=0,j=M;i<n;i++){vis[j]++;if(str[i]=='L'&&j-1!=stone) j--;if(str[i]=='R'&&j+1!=stone) j++;}if(vis[j]==0) return true;return false;
}int main()
{int i,j,m;scanf("%s",str);n=strlen(str);for(i=0,j=fl=fr=M;i<n;i++){vis[j]++;if(str[i]=='L'){j--;fl=min(fl,j);}else{j++;fr=max(fr,j);}}if(vis[j]==0){printf("1\n");return 0;}//printf("%d %d \n",fl,fr);if(str[n-1]=='L'){i=M; j=fr+1;while(i<=j){m=(i+j)/2;//printf("%d %d %d %d\n",i,j,m,yes(m));if(yes(m)){ans=m-M;i=m+1;}else j=m-1;}}else{i=fl-1; j=M;while(i<=j){m=(i+j)/2;//printf("%d %d %d %d\n",i,j,m,yes(m));if(yes(m)){ans=M-m;j=m-1;}else i=m+1;}}printf("%I64d\n",ans);return 0;
}
这篇关于CodeForces 404E Maze 1D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
