Codeforces Round#650 Div.3C.Social Distance의 연속적인 0 및 1 처리
6344 단어 codeforces
개요
예제
이렇게 생각했어요.
우선, 이렇게 아무도 없는 좌석이 n=7이라고 가정하면 k=2로 지정된다.이런 상황에서 ceil(n/(k+1))
사람이 가장 큰 좌석수인데 그림에서 보듯이 떠오른다.왜냐하면 먼저 왼쪽에 앉고 k가 비면 다시 바꾸는 것이 탐욕에 가장 적합하기 때문이다.
사람이 탈 수 있고 팔 수 있는 구간은 0연속 구간에 불과해 아무리 앉아도 옆 0연속 구간에 영향을 주지 않는다.즉, 연속된 0개 구간에 대해 상술한 계산을 할 수 있다.
맞다
그림에서 보듯이 4개의 빈 좌석이 있는 것을 감안하면 양쪽 끝은 특수 처리를 해야 한다.
from pprint import pprint
import sys
import itertools
def countstrs(s):
return [(k, len(list(g))) for k, g in itertools.groupby(s)]
import math
q = int(input())
for _ in range(q):
n,k = map(int, input().split())
s = input()
res = 0
dat = countstrs(s)
#print(dat)
l = len(dat)
for i in range(l):
ignoreLeft = False
ignoreRight = False
if i == 0:
ignoreLeft = True
if i == (l-1):
ignoreRight = True
if dat[i][0] == "1":
continue
cnt = dat[i][1]
if ignoreRight is False:
cnt -= (k)
if ignoreLeft is False:
cnt -= (k)
#print("space", cnt)
if cnt <= 0:
continue
res += math.ceil(cnt / (k+1))
print(res)
Reference
이 문제에 관하여(Codeforces Round#650 Div.3C.Social Distance의 연속적인 0 및 1 처리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/recuraki/items/a7de319bfe2b803b567a텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)