一种简洁有效的实现方案(可以快速 AC 民间数据)
查看原帖
一种简洁有效的实现方案(可以快速 AC 民间数据)
455777
algo_h楼主2024/12/1 14:23

假设 mamb 为题中表示两个字符串是否可以交换的向量,可以使用两个 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;
}
2024/12/1 14:23
加载中...