Si=1이 되는 임의의 i(i>=1)를 선택하여 S[i], S[i-1]의bit를 반전시키는 조작이 좋아하는 횟수
S와 T를 일치시킬 수 있으며, 가능하면 이를 위해 필요한 최소 조작 횟수
를 구한다.
구속
1 <= N <= 5*10-{5}
코드 커밋
from collections import deque
n =int(input())
s =input()
t =input()
q = deque()
ans =0for i inrange(n):if s[i]!= t[i]:if q:# q が空でない# print(i)if s[i]=="1":
ans += i - q.popleft()else:
q.append(i)else:
q.append(i)if q:print(-1)else:print(ans)
고찰하다.
우선 S[i]=1이 아니면 이런 제약을 반전시킬 수 없다는 것 이외에 고려
조작의 성질을 고려하면 같은 위치에서 두 번 반전하는 것은 무의미하다.
같은 곳에 대해 최대 한 번만 조작하기 때문에 S에서 연속적으로 반전 조작을 하는 곳을 하나의 구간으로 설정한다.
조작의 끝 얼굴, 한 구간이 원래의 배열에서 양쪽 문자만 반전하는 것을 알 수 있다.(다른 문자열은 두 번 반전되어 원래의 상태로 돌아갑니다)
S[i]=1의 제약을 받아 고려
한 구간에 대해 오른쪽 끝을 제외한 S[i]가 조작하는 동안 두 번의 반전
반전의 순서는 구간에 대한 전체 작업이 끝난 문자열과 무관하기 때문에 구간의 오른쪽 끝 이외의 구역에서 작업의 순서를 선택하여 반전할 때 S[i] = 1로 바꿀 수 있다.
구간의 오른쪽을 1 이외로 제한할 수 없기 때문에 필요에 따라 끼워 넣는 중 양쪽이 일치하지 않는 구간을 형성하여 구간의 오른쪽을 1로 한다.
실시 방침
왼쪽부터 차례대로 S를 핥는다.
queue에 S[i], T[i]와 다른 위치의 index
를 첨가
현재queue가 비어 있지 않은 상태에서 일치하지 않는 S[i]=1의queue에서 하나를 꺼내 i와 차별을 줍니다.S[i]=0이면 구간을 형성할 수 없으므로 i를queue
에 넣습니다.
다음의 반성
문자열 비교에서ifs[i]=1; 나는 구린내 나는 벌레를 낳았다...성장하지 못하다.
WA 이후 일주일 정도 재운 뒤 AC를 진행했습니다.
일치하지 않는 부분만 주목하고 구간 내에서 고려하면 된다는 것을 알아차린 후 오른쪽이 1인 조건을 탐욕적으로 어떻게 처리해야 할지 모른다
오른쪽의 1이 될 수 있으면 탐욕스럽게 처리할 수 있기 때문에 왼쪽의 부분을queue에 넣어서 해결할 수 있다
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
