C. Frog Jumps

Link

Solution

二分答案，贪心策略是跳到L后退1步，跳到R前进m步，如果跳到之前跳过的格子或跳回0说明无解，复杂度nlogn

Code

int vis[maxn];

bool judge(string&s, int d) {
    memset(vis, 0, sizeof(vis));
    int pos = d;
    vis[0] = 1;
    while (1) {
        if (vis[pos])return false;
        else {
            vis[pos] = 1;
            if (s[pos] == 'R') {
                pos += d;
                if (pos >= s.size())return true;
            }
            else pos--;
        }
    }
}

int solve(string &s) {
    int l = 1, r = s.size();
    while (l < r) {
        int m = (l + r) / 2;
        if (judge(s, m))r = m;
        else l = m + 1;
    }
    return l;
}

int main(int argc, char **argv) {
    int t;
    string s;
    cin >> t;
    while (t--) {
        cin >> s;
        s = "#" + s;
        cout << solve(s) << endl;
    }
    return 0;
}