#贪心 ## 题目大意 给定一个循环节 $s$，求给定的字符距离它右边最近的 $\texttt{g}$ 的距离，求最大值。 ## 思路 贪心，我们可以先思考没有循环。我们首先从前往后慢慢扫描，如果字符符合要求，我们就记录下这个字符的位置。这里我们只用记录**最小值**。 如果我们遇到了字符 $\texttt{g}$，那么直接记录答案，并且分节，因为这里是求最近的字符 $\texttt{g}$。 现在考虑循环。我们知道，相同的循环节如果我们直接记录，那么可能会存在跨过循环节的现象。但是我们知道，如果一个循环节里面有 $\texttt{g}$，那么不会存在两个循环节都找不到答案的情况；如果没有 $\texttt{g}$，则无解。我们只需将字符串拷贝一遍即可。 ## 判断贪心正确性 对于每一个给定的字符，它的右边只有一个答案。而如果没有分节，最小值肯定是最优的，没有必要把所有给定字符的位置全部记录下来，因为它距离右边的第一个 $\texttt{g}$ 肯定是最远的，因此这个贪心算法是完全正确的。 ## 代码 ```cpp #include <iostream> #include <cstring> // 使用string类进行操纵，可以更好地连接字符串 using namespace std; int t, n, ind = 1e9, ans = -1; // 细节*1：ind需要记录最小值，ans可能存在0的情况，保险 char c; string s; int main() { for (cin >> t; t; --t) { cin >> n >> c >> s; s += s /*调用string重载运算符拷贝字符串*/ , ans = -1, ind = 1e9; // 细节*2：多组数据记得清空！ for (int i = 0; i < s.size(); ++i) { //遍历每个字符 if (s[i] == c) { // 如果是开头 ind = min(ind, i); // 记录最优值 } if (s[i] == 'g') { // 细节*3：有可能给定字符就是g，不可写成else if ans = max(ans, i - ind); // 记录答案 ind = 1e9; // 细节*4：此时已经分节了，ind需要重新计算 } } cout << ans << '\n'; } return 0; } ```