CodeForces_1370E Binary Subsequence Rotationv(贪心)

Binary Subsequence Rotation

time limit per test：2 seconds memory limit per test：256 megabytes

Problem Description

Naman has two binary strings $s$s and $t$t of length $n$n (a binary string is a string which only consists of the characters “0” and “1”). He wants to convert $s$s into $t$t using the following operation as few times as possible.

In one operation, he can choose any subsequence of $s$s and rotate it clockwise once.

For example, if $s=1110100$s=1110100, he can choose a subsequence corresponding to indices (1-based) {2,6,7} and rotate them clockwise. The resulting string would then be $s=1010110$s=1010110.

A string $a$a is said to be a subsequence of string $b$b if $a$a can be obtained from $b$b by deleting some characters without changing the ordering of the remaining characters.

To perform $a$a clockwise rotation on a sequence $c$c of size $k$k is to perform an operation which sets $c_1:=c_k$c1​:=ck​,$c_2:=c_1$c2​:=c1​,$c_3:=c_2$c3​:=c2​,…,$c_k:=c_{k−1}$ck​:=ck−1​ simultaneously.

Determine the minimum number of operations Naman has to perform to convert s into t or say that it is impossible.

Input

The first line contains a single integer $n$n ($1≤n≤10^6$1≤n≤106) — the length of the strings.

The second line contains the binary string s of length $n$n.

The third line contains the binary string $t$t of length $n$n.

Output

If it is impossible to convert s to t after any number of operations, print −1.

Otherwise, print the minimum number of operations required.

Sample Input

6
010000
000001

Sample Output

1

题意

两个长度为n的01串s和t。可以进行任意次以下操作，从串s中选择一串子序列a，将a的元素后移一位，即$a_1 = a_k, a_2 = a_1,....,a_k=a_{k-1}$a1​=ak​,a2​=a1​,....,ak​=ak−1​。求最少需要多少次操作才能使串s与t相等。

题解

当s与t中字符’1’的数量相等时，有解；不等时，无解。
在进行操作是，对于两串原本就相同的部分无需移动，只需要处理不同的部分。每次选择的操作应该是1010…10或0101…01这两种形式（若有110或001这种形式，中间的元素实际上并未改变，两串还是不同的)。
贪心，若当前不同的字符为’0’，若存在最后一个字符为’1’的操作序列，则将‘0’加到此操作序列末尾；若不存在，则将此字符作为一个新的操作序列。'1’的情况同理。

#include<stdio.h>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<iterator>
#define dbg(x) cout<<#x<<" = "<<x<<endl;
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
#define eps 1e-6
   
using namespace std;
typedef long long LL;   
typedef pair<int, int> P;
const int maxn = 1000100;
const int mod = 10000;
char str1[maxn], str2[maxn];

int main()
{
    int n, i, j, k, sum1, sum2, num1, num2;
    sum1 = sum2 = 0;
    scanf("%d %s %s", &n, str1, str2);
    for(i=0;i<n;i++)sum1 += str1[i]-'0';
    for(i=0;i<n;i++)sum2 += str2[i]-'0';
    if(sum1 != sum2)printf("-1\n");
    else{
        num1 = num2 = 0;
        for(i=0;i<n;i++)
            if(str1[i] != str2[i]){
                if(str1[i] == '0'){
                    if(num1 != 0)num1--;
                    num2++;
                }else{
                    if(num2 != 0)num2--;
                    num1++;
                }
            }
        printf("%d\n", num1+num2);
    }
    return 0;
}