题解：AT_agc049_b [AGC049B] Flip Digits

· · 题解

贪心策略

我们先设数组 a 记录 s 中所有 1 的位置，b 记录 t 中所有 1 的位置，数量分别为 cnts 和 cntt。

判断无解

如果说 cnts < cntt 或者是 cnts - cntt 为奇数的话，这时候就无解了，就输出 -1。

匹配目标 1

我们从右向左，用一个指针 p 指向 a 的末尾，用另一个指针指针 j 指向 b 的末尾。

对于每个 b_j，我们取 a_p 处的 1 左移到 b_j，步数累加 a_p - b_j，然后 p \gets p-1，j \gets j-1。

如果说 p < 0 或 a_p < b_j，那就说明右边没有足够靠右的 1 来匹配这个，所以没有方法了，也就是无解了。

处理剩余 1

我们匹配完所有 b 后，s 中剩余的 1 位置为 a_0, a_1, \dots, a_p。这些 1 必须成对抵消，我们将 a_0 与 a_1、a_2，以此类推，进行配对，我们每对步数为 a_{i+1} - a_i，然后我们累加至答案。

所以最后总步数即为最小操作次数。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int n=5e5+5;
int a[n],b[n],cnt,cnt2;
int main() {
    int n;
    string s,t;
    cin>>n>>s>>t;
    for(int i=0;i<n;i++) if(s[i]=='1') a[cnt++]=i;
    for(int i=0;i<n;i++) if(t[i]=='1') b[cnt2++]=i;
    if(cnt<cnt2|(cnt-cnt2)%2) { cout<<-1<<endl; return 0;}
    long long ans=0;
    int p=cnt-1;
    for(int j=cnt2-1;j>=0;j--) {
        if(p<0||a[p] < b[j]){ 
        cout<<-1<<endl; return 0; 
        }
        ans+=a[p]-b[j];
        p--;
    }
    for(int i=0;i<p;i+=2) 
    ans+=a[i+1]-a[i];
    cout<<ans<<endl;
    return 0;
}