题解：AT_agc049_b [AGC049B] Flip Digits

· · 题解

题目概括

将一个子串用最少的次数反转成另一个子串。

思路

这种题肯定不能暴力（数据范围太大了），那就只能贪心了。

这道题因为是 01 串，所以只有两种情况，01->10 和 00->11。

贪心思路：从 1 到 n 遍历，如果不相同就要操作：找到离它最近的 1 一直向它取反过来，也就是通过 01->10 将 1 传过来。

还有，此题并不需要考虑顺序，所以贪心是对的。

提示：记得开 long long。

代码+注释

#include<bits/stdc++.h>
#define int long long//十年OI...，不开long long... 
using namespace std;
int n,b,ans;
char s[500010],t[500010];
signed main(){
    cin>>n>>s>>t;
    for(int i=0;i<n;i++){
        int pd=0,a=0;
        if(s[i]==t[i])continue;//只有不等于时才需要操作 
        for(int j=max(i+1,b);j<n;j++){
            if(s[j]=='1'&&!pd){//寻找离它最近的 1 
                a=j;
                break;
            }
        }
        b=a+1;
        if(b==1){//没有 1 了，所以无法完成 
            cout<<-1<<endl;
            return 0;//直接结束 
        }
        ans+=a-i;//a-i是每次操作所需步数 
        s[a]='0';//转换后 1 就变成 0 了 
        s[i]=t[i];//转换后两个子串的第 i 为也就相等了 
    }
    cout<<ans<<endl;
    return 0;
}