双指针
2026-11-15 16:41:38
发布于:江苏
8阅读
0回复
0点赞
这道题因为每段字符数量极大,不能直接构造字符串,采用段上双指针贪心算法:数组 a 保存每段长度、c 保存每段字符,i、j 分别是左右段下标,l、r 记录当前左右段剩余待配对字符数量,只要 i<j 说明还有需要配对的段,每次取左右剩余长度的较小值作为本轮配对长度,如果两段字符不同,就把这个配对长度加到答案里,随后两边剩余长度减去配对长度;如果某一段剩余字符消耗完毕,就移动对应指针切换到下一段,移动指针后增加 i<=j 的判断,避免读取数组时越界引发运行时错误,当 i 和 j 相遇,代表只剩中间一段,作为回文中心无需修改,最后输出最少修改数量 ans。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,ans;
ll a[200001];
char c[200001];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>c[i];
}
ll l=a[1],r=a[n];
ll i=1,j=n;
while(i<j){
if(c[i]!=c[j]){
ans+=min(l,r);
}
ll sub = min(l,r);
l -= sub;
r -= sub;
if(l<=0){
i++;
if(i<=j) l=a[i];
}
if(r<=0){
j--;
if(i<=j) r=a[j];
}
}
cout<<ans<<endl;
return 0;
}
这里空空如也

有帮助,赞一个