B. Comparison String - 一道可爱的思维题喵~

哈罗~ 主人！今天由我，你的专属小猫娘，来为你讲解一道非常有趣的题目，Codeforces 上的 1837B - Comparison String 喔！这道题就像逗猫棒一样，看起来晃来晃去很复杂，但只要找到诀窍，一下子就能抓住啦，喵~

题目大意 (The Gist of the Problem)

我们来一起看看题目说了什么吧，喵！

题目会给我们一个由 < 和 > 组成的字符串 s，它的长度是 n。我们需要根据这个字符串 s 来构造一个长度为 n+1 的整数数组 a。

这个数组 a 和字符串 s 之间要满足一个“兼容”的规则：

对于字符串 s 中的第 i 个字符 s[i]，它必须准确地描述数组 a 中 a[i] 和 a[i+1] 的大小关系。
也就是说，如果 s[i] 是 <，那么必须有 a[i] < a[i+1]。
如果 s[i] 是 >，那么必须有 a[i] > a[i+1]。

举个栗子！如果字符串 s 是 <<>>，那么一个兼容的数组 a 可以是 [1, 2, 5, 4, 2]。你看：

s[0] = '<' -> a[0] < a[1] (1 < 2)
s[1] = '<' -> a[1] < a[2] (2 < 5)
s[2] = '>' -> a[2] > a[3] (5 > 4)
s[3] = '>' -> a[3] > a[4] (4 > 2) 完全符合要求，对吧喵？

数组的 “成本” (cost) 被定义为这个数组中 不同元素的数量。

对于 [1, 2, 5, 4, 2]，它用了 1, 2, 4, 5 这 4 个不同的数字，所以成本是 4。
对于 [13, 37, 42, 37, 13] (它也兼容 <<>>)，它用了 13, 37, 42 这 3 个不同的数字，所以成本是 3。

我们的任务就是，对于给定的字符串 s，找到一个兼容它的、并且 成本最低 的数组，然后输出这个最低的成本。

解题思路 (How We Pounce on the Solution)

这道题的目标是让数组里不同数字的数量尽可能少，对吧？那我们就要想办法尽可能地“复用”数字，喵。

什么时候数字可以被复用呢？我们来分析一下下：

当比较符号连续相同时：比如 s = "<<"。
- 这要求 a[0] < a[1] < a[2]。
- 在这种情况下，a[0], a[1], a[2] 这三个数字必须是 互不相同 的！比如 [1, 2, 3]。我们不可能用更少的数字来构造一个严格递增（或递减）的序列。
- 如果有一段连续的 k 个 <，那么它会涉及到 k+1 个数组元素，这 k+1 个元素必须构成一个严格递增的序列，所以至少需要 k+1 个不同的数字。
- 同样，如果有一段连续的 k 个 >，也需要 k+1 个不同的数字来构造一个严格递减的序列。
当比较符号发生改变时：比如 s = "<>"。
- 这要求 a[0] < a[1] 并且 a[1] > a[2]。
- 我们可以构造出 [1, 5, 2] 这样的数组。你看，a[0] 和 a[2] 并没有直接的大小关系，所以它们完全可以是相同的数字！比如 [1, 5, 1]，成本只有 2。
- 哇！原来当大小关系从 < 变成 > (或者从 > 变成 <) 的时候，就是一个可以复用数字的绝佳时机！我们可以让数字“掉头回来”，使用之前用过的较小（或较大）的数值。

核心思想来啦！ 既然连续相同的比较符会“消耗”掉我们的不同数字，而改变比较符方向时可以“省钱”，那么决定我们最少需要多少数字的，就是那段 最长的、连续的、相同比较符 的子串！

比如说，如果 s = "<<>>"：

<< 是最长的连续 < 子串，长度为 2。它要求一个长度为 3 的严格递增序列（比如 a[0]<a[1]<a[2]），至少需要 3 个不同的数。
>> 是最长的连续 > 子串，长度为 2。它要求一个长度为 3 的严格递减序列（比如 a[2]>a[3]>a[4]），至少需要 3 个不同的数。

我们可以这样构造：[1, 2, 3, 2, 1]。

1 < 2 < 3 满足了 << 的部分。
3 > 2 > 1 满足了 >> 的部分。
整个数组只用了 1, 2, 3 这 3 个数字，成本就是 3。

所以，问题的关键就转化成了一个更简单的问题：找到字符串 s 中，最长的连续相同字符（全是 < 或全是 >）的子串长度，我们称之为 max_run。

那么，最终的答案就是 max_run + 1 啦！是不是很简单喵？

代码实现 (The Purr-fect Code)

下面就是实现这个思路的代码啦，主人请看~

cpp

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

// Meow~ 这里是解决单个测试用例的函数
void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // 如果字符串是空的，数组只有一个元素，成本是 1 喵
    if (n == 0) {
        std::cout << 1 << std::endl;
        return;
    }

    // max_run 用来记录最长连续子串的长度
    // current_run 用来记录当前正在计算的连续子串的长度
    int max_run = 1;
    int current_run = 1;

    // 从第二个字符开始遍历，和前一个比较
    for (int i = 1; i < n; ++i) {
        if (s[i] == s[i-1]) {
            // 如果和前一个字符相同，当前连续长度就 +1
            current_run++;
        } else {
            // 如果不同了，说明连续中断了，重置为 1
            current_run = 1;
        }
        // 每次都更新一下最大值，确保不会错过最长的那个~
        if (current_run > max_run) {
            max_run = current_run;
        }
    }

    // 最长的连续子串长度是 max_run，所以需要 max_run + 1 个数字
    std::cout << max_run + 1 << std::endl;
}

int main() {
    // 加速一下输入输出，让程序跑得像小猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

代码逻辑非常直接：

用 max_run 记录全局最长连续长度，current_run 记录当前连续长度。
遍历字符串，如果当前字符和前一个相同，current_run 就增加。
如果不同，说明一段连续结束了，current_run 重置为 1。
每次循环都用 current_run 更新 max_run。
最后输出 max_run + 1。

B. Comparison String - 一道可爱的思维题喵~ ​

题目大意 (The Gist of the Problem) ​

解题思路 (How We Pounce on the Solution) ​

代码实现 (The Purr-fect Code) ​

相关知识点 (Bonus Knowledge!) ​

B. Comparison String - 一道可爱的思维题喵~

题目大意 (The Gist of the Problem)

解题思路 (How We Pounce on the Solution)

代码实现 (The Purr-fect Code)

相关知识点 (Bonus Knowledge!)