Codeforces Round#650 Div.3C.Social Distance의 연속적인 0 및 1 처리

6344 단어 codeforces

개요

  • n열이 있는 의자는 n문자의 좌석 상황 s를 줄 수 있다.예를 들어, 10001.1 은 착석입니다.0은 빈자리입니다.
  • 사교 공간 때문에 k개의 빈자리를 비워야 앉을 수 있다.
  • 현재 사교 공간은 유지되고 있다.그럼 최대 몇 명이 앉을 수 있을까요?

    • 예제

  • k=1100010의 경우
  • 한 사람도 앉을 수 있어요.10101010 만들 수 있어요.
  • k=2가 000000일 경우
  • 두 사람이 더 앉을 수 있어요.100, 100 만들 수 있어요.
  • k=1이 10101인 경우
  • 더 이상 앉을 수 없다(0명).10101 밖에 못해요.

    • 이렇게 생각했어요.



    우선, 이렇게 아무도 없는 좌석이 n=7이라고 가정하면 k=2로 지정된다.이런 상황에서 ceil(n/(k+1))사람이 가장 큰 좌석수인데 그림에서 보듯이 떠오른다.왜냐하면 먼저 왼쪽에 앉고 k가 비면 다시 바꾸는 것이 탐욕에 가장 적합하기 때문이다.
    사람이 탈 수 있고 팔 수 있는 구간은 0연속 구간에 불과해 아무리 앉아도 옆 0연속 구간에 영향을 주지 않는다.즉, 연속된 0개 구간에 대해 상술한 계산을 할 수 있다.
    맞다

    그림에서 보듯이 4개의 빈 좌석이 있는 것을 감안하면 양쪽 끝은 특수 처리를 해야 한다.
  • 중간 상황을 고려한다.물론 비단 연속 0구간은 이 구간에 포함되지 않고 인접한 1구간은 1이다.따라서 양쪽 끝은 반드시 k의 거리를 비워야 한다.
  • 즉, 연속된 0의 수량이 l이면 이 구간은 (l-k-k)의 왼쪽 또는 오른쪽 끝에 1을 놓을 수 있는 구간으로 여겨져 위에서 말한 바와 같이 계산할 수 있다.
  • 예를 들어 왼쪽의 상황을 고려한다.이런 상황에서 오른쪽 옆집은 1이기 때문에 반드시 k의 거리를 비워야 한다.그러나 왼쪽 끝이 끝이기 때문에 가장 왼쪽에 1을 놓을 수 있다.오른쪽도 마찬가지예요.
    • 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)
    아르고 워크플로
    LeetCode 56. 병합 간격

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage