「MYOI-R3」字符串（字符串+模拟+思维+贪心）
发布时间
阅读量：
阅读量
「MYOI-R3」字符串
题目描述
给定字符串 s,t。
现在你要在 s,t 中删除一些字符并将它们重新排列使 s=t。
问操作后的 |s|（即字符串 s 的长度）最大是多少？
输入格式
第一行一个字符串 s。
第二行一个字符串 t。
输出格式
一行一个整数，表示操作后的 |s| 的最大值。
样例 #1
样例输入 #1
abc
bc样例输出 #1
2样例 #2
样例输入 #2
aaaaa
bbbbb样例输出 #2
0提示
在第一个样例中，将 a 删除，留下 bc。
此时 |s|=2，可以证明这是最优解。
在第二个样例中，将 aaaaa 删除，留下空串。
将 bbbbb 删除，留下空串。
此时 |s|=0，可以证明这是最优解。
本题采用捆绑测试 。
记 n=\max(|s|,|t|)。
| \text{Subtask} | n\le | 特殊性质 | 总分值 |
|---|---|---|---|
| 1 | 10 | 无 | 25 |
| 2 | 10^5 | \text{A} | 25 |
| 3 | 10^5 | \text{B} | 25 |
| 4 | 10^5 | 无 | 25 |
对于 100\% 的数据，1 \le |s|,|t| \le 10^5，字符串均由小写字母组成。
特殊性质 \text{A}：s 是一个 \text{a}\sim\text{z} 的排列。
特殊性质 \text{B}：保证 s_i,t_i\in\{\text{a},\text{b} \}。
细节
在本题中，变量 a,b 都会成为被删除的对象。
基于此，我们采用类似于桶排序的方法将这两个数组分别放入其中，并找出两者中的最小值点。
由于我们需要最大化 |s| 的值，在减少变化次数方面我们采取了最优策略。
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
string a,b;
int n1,n2;
int cnt1[30],cnt2[30];
int ans;
int main(){
cin>>a>>b;
n1=a.size(),n2=b.size();
//因为此时b也会删除
// int k=a.find(b);
// if(k==-1){
// cout<<"0";
// }else{
// cout<<n2;
// }
//此时我们用桶排序即可
for(int i=0;i<n1;i++){
cnt1[a[i]-'a']++;
}
for(int i=0;i<n2;i++){
cnt2[b[i]-'a']++;
}
for(int i=0;i<26;i++){
// if(cnt1[i]&&cnt1[i]==cnt2[i]){
// ans++;
// }
ans+=min(cnt2[i],cnt1[i]);
}
cout<<ans;
return 0;
}全部评论 (0)
还没有任何评论哟~