假设 ma 和 mb 为题中表示两个字符串是否可以交换的向量,可以使用两个 int 变量对每个可自由交换分块的 0 和 1 的数量分别进行计数,其中可自由交换的每个元素共享同一个 pair<int, int> 计数器(利用指针指向相同地址实现)。贪心算法实现过程中无需真正交换 0 和 1,直接扣减其分块中的计数即可。
void solve()
{
int n;
cin >> n;
string a, b, ma, mb;
cin >> a >> b >> ma >> mb;
vector<pair<int, int>> buf;
buf.reserve(2 * n);
vector<pair<int, int> *> sa(n), sb(n); // 每个可移动区的 0/1 计数
for(int i = 0; i < n; ++i) {
if(i == 0 || ma[i] == '0' || ma[i - 1] == '0') {
buf.emplace_back(0, 0);
sa[i] = &buf.back();
} else {
sa[i] = sa[i - 1];
}
if(a[i] == '0') {
++sa[i]->first;
} else {
++sa[i]->second;
}
}
// 以同样的方式处理 sb,具体步骤省略
// ...
// 贪心对齐
int ans = 0;
for(int i = 0; i < n; ++i) {
if(sa[i]->first && sb[i]->first) {
--sa[i]->first;
--sb[i]->first;
++ans;
} else if(sa[i]->second && sb[i]->second) {
--sa[i]->second;
--sb[i]->second;
++ans;
} else {
if(sa[i]->first) {
--sa[i]->first;
} else {
--sa[i]->second;
}
if(sb[i]->first) {
--sb[i]->first;
} else {
--sb[i]->second;
}
}
}
cout << ans << endl;
}