首页 > 试题广场 >

安置路灯

[编程题]安置路灯
  • 热度指数:43874 时间限制: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
头像 牛客题解官
发表于 2020-06-04 11:11:23
题目难度:二星考察点:贪心 分析:对于这道题来说,如果在第i个位置上安装路灯,那么它能够照亮的地方就是i-1, i和i+1,那么安装路灯最少的方法就是在三个位置的中间设置路灯,即如果第i个位置为'.', 那么显然在 i+1 处安装路灯是最好的,它可以照到位置i, i+1和i+2,这样能够最大程度的 展开全文
头像 美丽东
发表于 2020-03-27 15:36:51
使用贪心法,保证'.'在路灯照射的最左端。使用索引i遍历数组,发现'.'后,在i+1位置放置路灯,同时,i,i+1,i+2全部照亮,遍历从i+3位置继续。 代码如下: #include <iostream> #include <vector> using namespace 展开全文
头像 白色高跟鞋
发表于 2020-04-27 01:37:23
【Python15行】提供另一种思路:考虑使用队列+二进制编码来解,复杂度O(n)。贪心作为常规思路,在文末附上。 首先,枚举每三位可能的情况: 取【.】为1、【X】为0, 编成二进制,则点灯和不点等的情况为: 点灯: 4 5 6 7不点: 0 1 2 3 构建一个队列,从左往右扫描入列 展开全文
头像 白伟仝
发表于 2020-05-12 19:24:46
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = Integ 展开全文
头像 c小白进击之路
发表于 2021-04-07 09:07:47
#include<stdio.h> #include<malloc.h> int main() {     int t;scanf("%d",&t);     while(t--){    展开全文
头像 中科院在逃院士
发表于 2021-07-14 16:33:14
import java.util.*; public class Main { public static void main(String[] args){ Scanner sc=new Scanner(System.in); int 展开全文
头像 Mr.云sir
发表于 2020-02-27 17:09:20
题解 f[i]: 前i条道路至少需要安置的路灯数 按照道理i的状态划分: 如果为X, 不需要照亮,f[i] = f[i-1] 如果为., 一个路灯可以照亮三个位置,f[i] = f[i - 3] + 1; 代码 #include <iostream> using namespace 展开全文
头像 牛客338148058号
发表于 2022-04-04 22:27:45
创建游标移动查找,方法估计很多,能ac就行 n = int(input().strip()) for _ in range(n): m = int(input().strip()) z = input( 展开全文
头像 laglangyue
发表于 2020-05-14 23:27:38
思路很简单,滑动窗口扫描,扫描到‘.’直接跳过3个字符,安置一个路灯,扫描到‘X’,不处理跳过。主要注意多个测试用例,可以一边输入测试用例,一边输出结果。 import java.util.Scanner; public class Main { public static void ma 展开全文
头像 从那天开始
发表于 2020-08-19 01:43:06
import sys def find_x(x,i): if i>len(x)-1:return 0 if x[i] =='X': return find_x(x,i+1) elif x[i] =='.': return 1+find_ 展开全文