题解：CF2169B Drifting Away

· · 题解

CF2169B Drifting Away题解

主要题意

你要进行河上漂流旅行，路线由水流方向组合（一列字符）来决定：若为 > 就向右移一格；若为 < 就向左移一格；若为 * 就由你决定向左或向右走。

当你漂流到河外时，就算结束了旅行。

求出你最大旅行的时间（可能能无限航行，要判断）。

解题思路

首先，如果出现 *<，**，><，>* 这些水流组合时，就肯定可以无限航行了。

排除存在这些情况后，我们可以发现：一个水流组合中，最多只会出现一个 * 符号；且若出现 * 符号，整个水流组合就会被分为两段；否则就要么是一个只有向同一个方向的水流组合，要么是两段不同方向的水流组合。

这样，排除无限航行情况，有 * 符号的水流组合的最长时间就是连续的相同符号长度加一；否则就是整个序列的最长连续相同符号的长度。

上代码！

#include <bits/stdc++.h>
using namespace std;
string str;
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        cin >> str;
        int len = str.length();
        bool fg = 0;
        for(int i = 0;i < len;i ++)
        {
            if(
            str[i] == '*' && str[i + 1] == '<' || 
            str[i] == '*' && str[i + 1] == '*' || 
            str[i] == '>' && str[i + 1] == '<' || 
            str[i] == '>' && str[i + 1] == '*'
            )//可以无限航行的情况 
            {
                fg = 1;
                break;
            }
        }
        long long ans = 0;
        if(fg)
        {
            cout << -1 << endl;
            continue;
        }
        else
        {
            for(int i = 0;i < len;i ++)
            {
                if(str[i] == '*')//如果有 * 
                {
                    ans = max(i + 1, len - i);
                    fg = 1;
                    break;          
                }
                else if(i > 0 && str[i] != str[i - 1])//两段分别的长度 
                {
                    ans = max(i, len - i);
                    fg = 1;
                    break;  
                }               
            }
            if(!fg)//只有一种水流
                ans = len;
        }
        cout << ans << endl;
    }
    return 0;
}