题解：B4377 [蓝桥杯青少年组省赛 2025] 平衡奇偶位置的字符交换

· · 题解

前言

本蒟蒻在考场上这道题思考了20分钟才做了出来。

正文

这道题并非模拟题，而是找规律，我们先观察样例，

输入
AABABA
输出
1

因为奇数位置上的 A 的数量需要等于偶数位置上的 A 的数量。所以就需要将 A 的数量统计出来，再平分给奇数和偶数，如果A的数量是奇数，就代表平分不了，按照题目要求输出 -1 即可。

如果 A 的数量是偶数，就需要将 A 的总数平分，减去奇偶个数中较小的那个数，就是需要 A 和 B 交换的次数。即 (a+b)/2-\min(a,b) 注：a 为奇数位置上的 A 的数量，b 为偶数位置上的 A 的数量。

如这个样例（自创）：

输入
AABABABABA
输出
2

A的数量为 6 个，奇数位上有 1 个，偶数位上有 5 个 ，故算式为 (5+1)/2-1 = 2 。

操作：

  1. 交换位置 2 和 3 的字符（A 和 B）
  2. 交换位置 4 和 5 的字符（A 和 B）

此时奇数位上有 3 个 A，偶数位上有 3 个 A，故需交换两次。与计算结果相同。

Code：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string a;
    int sum = 0,cnt = 0; 
    cin>>a;
    int len = a.length();
    for(int i = 0;i<len;i++){//统计奇偶个数 
        if(a[i] == 'A'){
            if((i+1)%2 == 1){//+1是因为位置编号从 1 开始
                sum++;
            }else if((i+1)%2 == 0){
                cnt++;
            }
        }
    }
    if((sum+cnt)%2 == 1){//无法平分，输出-1 
        cout<<-1;
    }else{
        cout<<(sum+cnt)/2-min(sum,cnt);//先平分，再减去小的那个，就算是交换次数 
    }
    return 0;
}