题解：CF2149D A and B

_GIGjqw12_ · 2025-11-30 19:22:15 · 题解

方法思路

问题分析：

• 目标是将所有 'a' 或所有 'b' 集中成一个连续块,最小化相邻交换次数。
• 相邻交换的次数等价于字符在原字符串中的位置与目标连续位置之间的逆序数。

  核心观察：

• 对于字符 'a',假设共有 c 个,它们在原字符串中的位置为 p。目标位置为 [k, k+1,\dots,k+c-1] (其中 k 是起始位置),最小交换次数为这些位置的逆序数。
• 同理,对于字符 'b',计算其位置的逆序数。
• 最终结果为两种字符逆序数的最小值。

  算法选择：

• 收集 'a' 和 'b' 在原字符串中的位置。
• 计算每种字符位置列表的逆序数(通过计算每个位置与目标连续位置的差值之和)。
• 比较两种逆序数,取最小值作为结果。

  解决代码

  
  #include <iostream>
  #include <vector>
  #include <string>
  #include <algorithm>  

using namespace std;

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

int t;
cin >> t;
while (t--) {
    int n;
    string s;
    cin >> n >> s;

    vector<int> a, b;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'a') {
            a.push_back(i);
        } else {
            b.push_back(i);
        }
    }
    long long ca = 0;
    for (int i = 0; i < a.size(); ++i) {
        ca += a[i] - i;
    }
    long long cb = 0;
    for (int i = 0; i < b.size(); ++i) {
        cb += b[i] - i;
    }
    cout << min(c, cb) << '\n';
}

return 0;

}