首页 > 试题广场 >

放置路灯

[编程题]放置路灯
  • 热度指数：945 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小Q正在给一条长度为n的道路设计路灯安置方案。
为了让问题更简单,小Q把道路视为个方格,需要照亮的地方用 '.' 表示, 不需要照亮的格子用 'X' 表示。
小Q现在要在道路上设置一些路灯, 对于安置在 位置的路灯, 这盏路灯可以照亮 这三个位置。
但是有个限制，不需要照亮的格子上面不能放置路灯。
小Q希望能安置尽量少的路灯照亮所有 '.' 区域, 希望你能帮他计算一下最少需要多少盏路灯。

输入描述:
第一行一个正整数 
第二行为一个长度为 的字符串，仅由 '.' 和 'X' 这两种字符组成。
数据范围：


输出描述:
最少需要放置的路灯数量
示例1

输入

5
.X.X.

输出

3

说明

由于不需要照亮的格子上面不能放置路灯，所以必须在1,3,5这三个位置放置路灯
示例2

输入

5
.....

输出

2

说明

在2,4这两个位置放置路灯即可。
算法知识视频讲解
开通博客
头像 牛客847048975号
发表于 2021-04-17 15:48:11
一遍贪心 #include<iostream> #include<string> #include<vector> #include<unordered_map> #include<algorithm> #include<time.h 展开全文
去ta的博客 赞 (1) 回复(1) 收起

问题信息

上传者：小小
难度：
0条回答 965浏览

热门推荐

通过挑战的用户

相关试题

放置路灯

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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