我要招人

去企业版

首页 > 试题广场 >

安置路灯

[编程题]安置路灯

热度指数：43876 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小Q正在给一条长度为n的道路设计路灯安置方案。

为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用'.'表示, 不需要照亮的障碍物格子用'X'表示。

小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。

小Q希望能安置尽量少的路灯照亮所有'.'区域, 希望你能帮他计算一下最少需要多少盏路灯。

输入描述:

输入的第一行包含一个正整数t(1 <= t <= 1000), 表示测试用例数
接下来每两行一个测试数据, 第一行一个正整数n(1 <= n <= 1000),表示道路的长度。
第二行一个字符串s表示道路的构造,只包含'.'和'X'。

输出描述:

对于每个测试用例, 输出一个正整数表示最少需要多少盏路灯。

示例1

输入

2
3
.X.
11
...XX....XX

输出

1
3

算法知识视频讲解

Python

Treamy

一开始使用动态规划递归来做：

f(i)每次返回s[:i]需要的路灯数和最后一盏灯的位置，

在i+1的逻辑中，判断如果是`.`且s[:i]最后一盏灯不在i，则返回s[:i]需要的路灯数+1和i+1的位置；如果是s[:i]最后一盏灯的位置在i+1，则返回s[:i]需要的路灯数和i

但这样错误。

再次分析，得使用大小为3的滑动窗口，且该窗口的开头必须为`.`，若遇到`X`的开头直接跳过，因为其不需要被照亮，也不需要被考虑。当窗口内元素为3个时：

然后考虑以`.`开头的窗口有`...`, `..X`, `.X.`, `.XX`这四种可能，只需要在中间放一个灯就可以满足该窗口了。

当滑到结尾时，可能刚好滑完，也可能还剩一个`.` 或剩两个的`.X`, `..`，这时还需要一个灯满足该小窗口。

具体代码如下：

test_num = int(input())
while test_num > 0:
    n = int(input())
    s = list(input())
    cnt = 0
    i = 0
    # 大小为3的滑动窗口滑动
    while i < n:
        if s[i] == 'X': # 第一个为X，直接滑动1滑过该位置
            i += 1
        else: 
            if i+2>=n: # 窗口不足3了
                break
            # 否者为 ...或..X或.X.或.XX，这时需要一个路灯放在中间即可照亮该窗口
            cnt += 1
            i += 3 # 滑动3个位置
    if i == n: # 刚好滑完
        print(cnt)
    else: # 可能是..或.X或. 还需要一个路灯
        print(cnt+1)
    test_num -= 1

提交正确，速度也还可以。

这是贪心吗？

发表于 2021-03-19 17:41:34 回复(0)

Python

12313242

python3:

t = eval(input())
for i in range(t):
    n = eval(input())
    road = list(input())
    count = 0
    for j in range(1,n-1):
        if road[j-1] =='.':
            count += 1
            road[j],road[j+1] = 'X','X'
    if road[n-2] == '.'or road[n-1] == '.':
        count += 1
    print(count)

编辑于 2020-09-21 13:48:43 回复(0)

Python

风201906272038276

道路从第一个开始为 ‘ . ’时，灯（a） + 1

如果不是则道路(j) +1

当道路走完时输出灯的个数 num=【】多余

t=int(input())

num=[]
for i in range(t):
n=int(input())
s=input()
a=0
j=0
while j<n:
if s[j] == '.':
a+=1
j+=3
else:
j+=1
num.append(a)
print(num)

发表于 2019-10-07 16:54:30 回复(0)

Python

K总

import sys
n=int(sys.stdin.readline().strip())
list1=[]
list2=[]
for i in range(n):
list1.append(int(sys.stdin.readline().strip()))
list2.append(str(sys.stdin.readline().strip()))
for i in range(n):
count=0
j=0
ll=list(list2[i])
while(j<list1[i]):
if ll[j]=='.':
j+=3
count+=1
else:
j+=1
print(count)

发表于 2019-08-27 15:36:19 回复(0)

Python

国企程序锅

# Python Solution
# 智力题
# 碰到'.', i = i + 3


while True:
    try:
        g = int(input())
        for _ in range(g):
            m = int(input())
            strs = input()
            i = 0
            num = 0
            while i < m:
                if strs[i] == '.':
                    i = i + 3
                    num = num + 1
                else:
                    i = i + 1
            print(num)
    except:
        break

发表于 2019-08-19 18:43:50 回复(0)

Python

秋山澪

'''
动态规划
当前为i，则为前面第三个的值加1
当前为X，则和前面一个值一样
s[i]=="."  dp_lst[i]=1 if i<=2 else  dp_lst[i-3]+1
s[i]=="X"  dp_lst[i]=0 if i==1 else dp_lst[i-1]
'''
import sys
t=int(sys.stdin.readline().strip())
for _ in range(t):
    n=int(sys.stdin.readline().strip())
    s=sys.stdin.readline().strip()
    dp_lst=[0 for i in range(n)]
    for i in range(n):
        if s[i]==".":
            if i<=2:
                dp_lst[i]=1
            else:
                dp_lst[i]=dp_lst[i-3]+1
        else:
            if i==0:
                dp_lst[i]=0
            else:
                dp_lst[i]=dp_lst[i-1]
    print(dp_lst[n-1])

发表于 2019-08-14 09:37:07 回复(0)

Python

菜鸡别说话

try:
    while True:
        t = int(input())
        while t > 0:
            n = int(input())
            s = input()
            
            #遇到'X'每次走一步，遇到'.'每次走三步
            res = 0
            j = 0
            while j < len(s):
                if s[j] == '.':
                    j += 3
                    res += 1
                else:
                    j += 1
                         
            print(res)
                
            t -= 1
except:
    pass

发表于 2019-08-04 19:36:08 回复(0)

Python

offer快快来offer

import sys
k = sys.stdin.readline()
k = int(k)
for i in range(k):
n = int(sys.stdin.readline())
st = list(sys.stdin.readline())
j = 0
m = 0
while j<=n:
if(st[j]=="."):
m = m+1
j = j+3
else:
j = j+1
print(m)

发表于 2019-08-03 19:52:36 回复(0)

Python

欧巴禾

while True: try:
        n = int(input()) for i in range(n):
            m = int(input())
            string = input()
            count = 0  index = 0  while index<len(string): if string[index]=='.':
                    count+=1  index +=3  else:
                    index+=1  print(count) except: break

发表于 2019-07-21 23:25:01 回复(0)

Python

水君201903172004868

t = int(input())
for i in range(t):
    n = int(input())
    s = input()
    ans = 0
    j = 0
    while j < n:
        if s[j] == '.':
            ans += 1
            j += 3
        else:
            j += 1
    print(ans)

发表于 2019-06-22 18:29:18 回复(3)

Python

傩诺1

每次遇见'.'就往前跳3格，路灯数量+1，遇到'X'就往前跳1格，路灯数量不变

t = int(raw_input())
for i in range(t):
    n = int(raw_input())
    s = raw_input()
    light = 0
    i = 0
    while(i < n):    
        if s[i] == '.':        
            light += 1        
            i += 3    
        else:        
            i += 1    
    print light

发表于 2018-03-29 00:54:33 回复(0)