题解
2026-10-31 16:41:46
发布于:上海
126阅读
0回复
0点赞
题意
给定一个,个和n个,表示的个数,由这些字符依次组成一个字符串,你能将任意一个小写字符变为另一个小写字符,求最小改变的字符数
暴力
按题意拼成一个字符串比较,很简单,代码如下
#include<iostream>
using namespace std;
const int N=2e5+5;
int main(){
int n,a[N];
char c[N];
cin>>n;
string s=" ";
for(int i=1;i<=n;i++){
cin>>a[i]>>c[i];
for(int j=1;j<=a[i];j++)s+=c[i];
}
long long cnt=0;
int len=s.size()-1;
for(int i=1;i<=len/2;i++)
if(s[i]!=s[len-i+1])cnt++;
cout<<cnt;
return 0;
}
正解
我是用了一个双指针,分别为,比较前后字符不同的数量,如果个比较完则,同理如果个比较完则
比较时字符不同的个数相加起来就是最后的答案,代码如下
#include<iostream>
using namespace std;
const int N=2e5+5;
int n,a[N];
char c[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i]>>c[i];
int l=1,r=n;
long long cnt=0;
while(l<=r){
if(c[l]!=c[r]){
if(a[l]>a[r]){
cnt+=a[r];
a[l]-=a[r];
r--;
}else if(a[l]==a[r]){
cnt+=a[l];
l++,r--;
}else{
cnt+=a[l];
a[r]-=a[l];
l++;
}
}else{
if(a[l]>a[r]){
a[l]-=a[r];
r--;
}else if(a[l]==a[r]){
l++,r--;
}else{
a[r]-=a[l];
l++;
}
}
}
cout<<cnt;
return 0;
}
全部评论 2
难度评测低了
2026-11-01 来自 广东
0智齿
2026-10-31 来自 浙江
0







有帮助,赞一个