2 条题解
-
0
思路:先记录每一段金奖杯的始末位置,然后考虑他们连接的问题
#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
- 上传者