首页 > 试题广场 >

安置路灯

[编程题]安置路灯
  • 热度指数:40 时间限制: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
这边给一个我的思路,首先X不用照亮,我们看到X就跳过即可,然后用一个快慢指针,用他们的差记录需要照亮位置的数目,然后直接用size / 3.0向上取整就可以了。。
至于为何用size / 3.0向上取整,这边考虑一下所有情况
①当size = 1,应该只用放一个路灯
②当size = 2,路灯放左边可以照亮右边,只用一个灯
③当size >=3 ,贪心思维,一个路灯最多可照亮3个,如果需要照亮的位置小于3,那么需要一个灯,
例如需要照亮的地方为5,即为.....记为s,此时灯放在s[1]可照亮0,1,2,剩下两个还需要照亮的地方,因为是向上取整所以5/3.0 = 2,正好多出一盏灯照亮他们

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution323 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        Integer len = Integer.parseInt(reader.readLine());
        String s = reader.readLine();
        int pos = 0;
        int res = 0;
        int fast = 0;
        while(fast < len){
            if(s.charAt(pos) == 'X'){
                pos++;
                fast++;
                continue;
            }
            while(fast < len && s.charAt(fast) == '.'){
                fast++;
            }
            int size = fast - pos;
            res += Math.ceil(size / 3.0);
            pos = fast;
        }
        System.out.println(res);
    }
}


发表于 2022-03-14 12:35:31 回复(0)