首页 > 试题广场 >

安置路灯

[编程题]安置路灯
  • 热度指数：43977 时间限制：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头像 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头像 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头像 风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总头像 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头像 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头像 水君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头像 傩诺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)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 数组 运维工程师 字符串 前端工程师 算法工程师 测试工程师 PHP工程师 贪心 模拟 网易 2019 Java工程师
来自：网易2019实习生招聘...
上传者：小小
难度：
15条回答 29223浏览

热门推荐

通过挑战的用户

查看代码

相关试题

安置路灯

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号