1 条题解

  • 0
    @ 2026-1-28 12:33:10
    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        // [1] n-输入字符串的长度(1≤n≤1000)
        int n;
        cin>>n;
        // [2] s1-目标字符串,s2-需要翻转操作的源字符串(仅包含'H'和'G')
        string s1,s2;
        cin>>s1>>s2;
        // [3] i-左指针(从字符串左端开始,初始为0);j-右指针(从字符串右端开始,初始为n-1)
        int i=0,j=n-1;
        // [4] sum-记录最少翻转次数,初始为0
        int sum=0;
    
        // [5] 双指针循环:从两端向中间遍历,处理字符匹配问题
        while(i<=j){
            // [6] 情况1:左右两端的字符都与目标字符串不匹配
            // 逻辑:翻转i到j的子串可同时修正两端的不匹配,减少翻转次数,符合“最少翻转”的目标
            if(s1[i]!=s2[i] && s1[j]!=s2[j]){
                // [7] 执行翻转操作:将i到j区间内的'H'和'G'互转
                for(int k=i;k<=j;k++){
                    if(s2[k]=='H') s2[k]='G';
                    else s2[k]='H';
                }
                // [8] 翻转后,左右指针向中间移动,翻转次数+1
                i++,j--;
                sum++;
            // [9] 情况2:左指针字符不匹配,右指针字符匹配
            // 逻辑:仅左不匹配,缩小右指针范围,尝试让左不匹配的字符与后续区间一起翻转
            }else if(s1[i]!=s2[i] && s1[j]==s2[j] ){
                j--; 
            // [10] 情况3:左指针字符匹配,右指针字符不匹配
            // 逻辑:仅右不匹配,缩小左指针范围,尝试让右不匹配的字符与后续区间一起翻转
            }else if(s1[i]==s2[i] && s1[j]!=s2[j] ){
                i++; 
            // [11] 情况4:左右两端字符都匹配,直接向中间移动指针
            }else{
                i++,j--;
            }
        } 
        // [12] 输出最少翻转次数
        cout<<sum;
        return 0;
    }
    
    • 1

    信息

    ID
    1030
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    5
    已通过
    1
    上传者