题意：指令“R”机器人会向右走一步，“L”是向左。起初机器人在0位置，可以在除了0以外的任何位置放障碍，如果机器人的指令将使它走到障碍上，那这一步他会保持不动。要求让机器人最终结束的那一步一定只走过一次，也就是最后一次，这样称为完成指令。求在放障碍最少的情况下，能使机器人完成指令的方案数。
方法：
我去，这题意略长啊。
最开始从细节分析，然后枚举情况，感觉挺简单的，然后……就没有然后了……后面枚举情况的时候，好复杂，感觉怎么都想不全（至少短时间想不全诶）
然后看解题宝宝。（是报告）额，原来可以用模拟+二分解决~
真是暴力的思路呀，不过没有发现它的二分性质~
诶，以后要从暴力的方面先想象咯，或者，太复杂的时候，看看有没有简单的方法。。
好吧，怎么说就是，，，自己二分太弱。。
（我去，这解题报告写的都是什么。。。。。你是因为今天都没交所以占位的么。。哎哟我去）。。
代码
#include <cstdio> #include <cstring> int len; char str[1000010]; bool testBlock(int pos) { int now = 0; int left = 0; bool isNewLeft = true; for (int i = 0; str[i]; i++) { if (str[i] == ‘R‘) { isNewLeft = false; if (now+1 == pos) ; else now++; } else now--; if (now < left) { left = now; isNewLeft = true; } } return isNewLeft; } int main() { while (scanf("%s", str) != EOF) { len = strlen(str); if (str[len-1] == ‘R‘) { for (int i = 0; str[i]; i++) { if (str[i] == ‘R‘) str[i] = ‘L‘; else str[i] = ‘R‘; } } if (testBlock(len+5)) { puts("1"); continue; } int l = 0; int r = len+5; while (l<r) { int mid = (l+r+1)/2; if (testBlock(mid)) l = mid; else r = mid-1; } printf("%d\n", l); } return 0; }
Codeforces 404E: Maze 1D(二分),布布扣,bubuko.com
原文：http://www.cnblogs.com/shinecheng/p/3614797.html