日常一道算法题。

翻译

社会隔离

Polycarp 和他的朋友想要参观一个餐厅。餐厅有 n 个座子，排成一列。已经有一些客人坐在位置上，座位的编号为从 1 到 n。餐厅座位的状态被描述成 0 和 1，0 表示没有客人，1 表示有客人。

餐厅要求任何客人之间的距离最小间隔 k 个桌子。如果一个客人坐在了 i 位置，那么从 i - k 到 i + k 不能有别的客人。

你需要计算，目前餐厅最多能接待多少客人。

输入格式

第一行输入整数 t，表示测试用例组数。

每个测试用例输入两行，第一行输入整数 n 和 k。第二行输入长度为 n 的字符串，只包含 0 和 1。

输出格式

输出一个整数，表示可以接待客人的数量。

分析

模拟题很简单，遍历一遍字符串即可，并且标记当前开头是否是 1，每段连续 0 分别判断开头是否是 1，结尾是否是 1。

如果开头是 1，那么连续 0 的长度减 k，如果结尾是 1，长度也减 k。

然后长度除以 k 表示可以放置 1 的个数，如果长度不能整除k，个数再加 1。

最后输出总和。

代码(Python3)

# https://codeforces.com/problemset/problem/1367/C
 
import sys
import os
import heapq
import math
 
try:
    path = "./file/input.txt"
    if os.path.exists(path):
        sys.stdin = open(path, 'r')
    # sys.stdout = open(r"./file/output.txt", 'w')
except:
    pass
 
t = int(input())
 
def printd(value):
    # print(value)
    pass
 
def case():
    arr = list(map(int, input().split(" ")))
    n, k = arr[0], arr[1]
    arr = input()

    startOne = False
    length = 0
    result = 0
    for value in arr:
        if value == '1':
            length = max(0, length - k)
            if startOne:
                length = max(0, length - k)
            result += length // (k + 1) + (1 if length % (k + 1) > 0 else 0) 
            startOne = True
            length = 0
        else:
            length += 1

    if startOne:
        length = max(0, length - k)
    result += length // (k + 1) + (1 if length % (k + 1) > 0 else 0)

    print(result)

for _ in range(t):
    case()

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.06.30 长春