codeforce每日一题链接

题目描述

给你一个字符串，每个字符不是$’<’$，就是$’>’$。有一个数组$a$，$s[i]$为$’<’$表示a[i] < a[i+1]，$s[i]$为$’>’$表示$a[i]>a[i+1]$，请返回$a$的最小代价。数组的代价是数组中不同元素的数量。

样例

输入样例1

4
4
<<>>
4
>><<
5
>>>>>
7
<><><><

输出样例1

3
3
6
2

算法

(暴力枚举) $O(n)$

找出最大连续的’<’或者’>’的长度，答案就是最大长度加1。

C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;

inline void solve()
{
    cin>>n;
    string str;
    cin>>str;
    int res = 0;
    for(int i=0;i<n;i++){
        int j = i;
        while(j<n && str[j]==str[i]) j++;
        res = max(res, j - i);
        i = j - 1;
    }

    cout<<res + 1<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }

    return 0;
}