博客主页:PH_modest的博客主页
当前专栏:每日一题
其他专栏:
每日反刍
* C++跬步积累
* C语言跬步积累
座右铭:广积粮,缓称王!
一.题目描述
题目大意:
弗拉德找到了一个由 n n n 个小写拉丁字母组成的字符串 s s s ,他想让这个字符串越短越好。
为此,他可以从 s s s 中任意删除对相邻的字符,只要它们不同。例如,如果 s s s =racoon,那么通过删除一对字符,他可以得到coon、roon、raon和raco字符串,但他不能得到racn(因为删除的字母相同)或rcon(因为删除的字母不相邻)字符串。
弗拉德通过任意数量的删除可以得到的最小长度是多少?
题目链接:
C. Removal of Unattractive Pairs(Codeforces Round 913 (Div. 3))
二.思路分析
- 从最后的结果推结论:最后的结果肯定是两种:①没有字符剩下,全都能消除;②只剩下一种字符
- 因此可以得出最后剩下的数字肯定是数量最多的那个字符,所以只需要统计出现次数最多的那个字符就可以了,然后分情况讨论
注意讨论奇偶的情况
三.代码展示
//https://codeforces.com/contest/1907/problem/C
//从结果往前推,最后肯定是只剩一个字符或者没有字符,只需要考虑出现次数最多的就可以了
//
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
#include<deque>
#include<vector>
#include<cstring>
#define int long long
using namespace std;
map<char,int>mp;
void solve()
{
mp.clear();
int n;
cin>>n;
string s;
cin>>s;
int maxx=0;
for(int i=0;i<n;i++)
{
mp[s[i]]++;
}
for(char i='a';i<='z';i++)
{
maxx=max(maxx,mp[i]);
}
if(maxx<=n/2)
{
if(n%2==1)
{
cout<<"1"<<"\n";
}
else
{
cout<<"0"<<"\n";
}
}
else
{
cout<<maxx-(n-maxx)<<"\n";
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
最后:
每日一题系列旨在养成刷题的习惯,所以对代码的解释并不会特别详细,但足够引导大家写出来,选的题目都不会特别难,但也不是特别简单,比较考验大家的基础和应用能力,我希望能够将这个系列一直写下去,也希望大家能够和我一起坚持每天写代码。
之后每个星期都会不定期更新codeforces和atcoder上的题目,想要学习算法的友友们千万别错过了,有什么疑问欢迎大家在评论区留言或者私信博主!
在这里送大家一句话:广积粮,缓称王!
文章评论