小Q正在给一条长度为n的道路设计路灯安置方案。为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用’.’表示, 不需要照亮的障碍物格子用’X’表示。小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos – 1, pos, pos + 1这三个位置。小Q希望能安置尽量少的路灯照亮所有’.’区域, 希望你能帮他计算一下最少需要多少盏路灯。

区块链毕设网qklbishe.com为您提供问题的解答

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

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

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

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

这边给一个我的思路，首先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);     } }

35:31

以上就是关于问题小Q正在给一条长度为n的道路设计路灯安置方案。为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用’.’表示, 不需要照亮的障碍物格子用’X’表示。小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos – 1, pos, pos + 1这三个位置。小Q希望能安置尽量少的路灯照亮所有’.’区域, 希望你能帮他计算一下最少需要多少盏路灯。的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。

区块链NFT链游项目方科学家脚本开发培训