题目:
样例:
|
3 3 6 2 |
思路:
由题意,条件是
又因为要使用尽可能少的数字,这是一道贪心题,所以我们可以知道,
当遇到符号相同的时候,肯定只能使用新的数字,即 使用的数字数量积累,累加 ++cnt,然后ans 取我们尽可能使用的数字数量 ans = max(ans,cnt)
当遇到不同的符号的时候,我们可以用之前使用过的数字,避免数字数量的累加,即重回刚开始的数字, cnt = 1 数字积累量重置
代码详解如下:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) (x).begin(),(x).end()
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;inline void solve()
{string s;int n;cin >> n >> s;int cnt = 1; // 肯定有一个数字做开头int ans = cnt; // 存储我们尽可能使用的数字数量for(int i = 1;i < n;++i){if(s[i] == s[i - 1]){// 如果遇到符号相同// 肯定需要新的数字++cnt;}else cnt = 1; // 否则我们使用最初的数字,达到重置重新累计的效果,尽可能用重复的数字ans = max(ans,cnt);}// 最后的 ++ans 是累计我们最后会用到的数字++ans;cout << ans << endl;
}signed main()
{
// freopen("a.txt", "r", stdin);___G;int _t = 1;cin >> _t;while (_t--){solve();}return 0;
}