2 条题解

  • 0
    @ 2025-10-14 11:27:47

    思路:先记录每一段金奖杯的始末位置,然后考虑他们连接的问题

    #include <iostream>
    #include <vector>
    using namespace std;
    
    // 每一段金奖杯的始末位置 
    struct strInfo
    {
        int beginIndex = 0, endIndex = 0;
        strInfo(int a, int b)
        {
            beginIndex = a;
            endIndex = b;
        }
    
        int getLength()
        {
            return endIndex - beginIndex + 1;
        }
    };
    
    int main()
    {
        int n; 
        cin >> n;
        char str[n];
        int beginIndex = 0, endIndex = 0;
        vector<strInfo> Infos;
        for (int i = 0; i < n; i++)
        {
            cin >> str[i];
            if (str[i] == 'G')
            {
                endIndex = i; // 向后挪末位置 
            }
            else if (str[i] == 'S') // 遇到银奖杯,记录上一段金奖杯的末位置 
            {
                if (beginIndex != endIndex || str[beginIndex] == 'G' /* 这一段金奖杯只有一个的情况 */)
                {
                    Infos.push_back(strInfo(beginIndex, endIndex));
                }
                // 重置下一段金奖杯位置 
                beginIndex = i + 1;
                endIndex = i + 1;
            }
        }
    
    	// 记录最后一段金奖杯的位置 
        if (str[n - 1] == 'G')
        {
            Infos.push_back(strInfo(beginIndex, endIndex));
        }
    
    	// 没有金奖杯 
        if (Infos.size() == 0)
        {
            cout << 0 << endl;
            return 0;
        }
        else if (Infos.size() == 1) // 只有一段金奖杯 
        {
        	// 直接输出这一段金奖杯的长度 
            cout << Infos[0].getLength() << endl;
            return 0;
        }
    
        bool hasCloseStr = false; // 标记是否有紧挨着的两端金奖杯 如:GGGSGGS 
        int maxSingleStrLength = 0; // 记录单端最长的金奖杯长度 
    
        for (size_t i = 0; i < Infos.size(); i++)
        {
            if (Infos[i].getLength() > maxSingleStrLength)
            {
                maxSingleStrLength = Infos[i].getLength(); // 获取最长长度 
            }
        }
    
        vector<int> closeStrIndex; // 若金奖杯段a和b紧挨着(b在a之后),记录a在Infos中的索引 
    
        for (size_t i = 0; i < Infos.size() - 1; i++)
        {
            if (Infos[i + 1].beginIndex - Infos[i].endIndex == 2)
            {
                hasCloseStr = true;
                closeStrIndex.push_back(i);
            }
        }
    
    	// 若没有紧挨着的金奖杯则输出最长的一段长度+1(因为可以挪一个金奖杯过来) 
        if (!hasCloseStr)
        {
            cout << maxSingleStrLength + 1 << endl;
            return 0;
        }
    
        int ans = 0;
        for (size_t i = 0; i < closeStrIndex.size(); i++)
        {
            int length = Infos[closeStrIndex[i]/* 前面提到的金奖杯段a的索引 */].getLength() + 
    					Infos[closeStrIndex[i] + 1/* 金奖杯段b的索引 */].getLength(); // a 和 b 的总长度(因为相邻,所以可以挪动a或b中的一个金奖杯将两段合二为一) 
            if (length > ans)
            {
                ans = length;
            }
        }
    
        if (Infos.size() == 2) // 只有两段金奖杯,且他们紧挨着 
        {
            cout << ans << endl;
        }
        else
        {
            if (maxSingleStrLength > ans) // 连续两段还没有最长的单段长 
            {
                cout << maxSingleStrLength + 1 << endl;
                return 0;
            }
            
            // 有2段以上金奖杯,可以从其他地方挪一个金奖杯来连接最长的两段金奖杯,所以ans+1 
            cout << ans + 1 << endl;
        }
            
        return 0;
    }
    

    信息

    ID
    307
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    691
    已通过
    73
    上传者