小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链游项目方科学家脚本开发培训

承接区块链项目定制开发

微信:btc9767

QQ :1330797917

TELEGRAM: BTCOK9

承接区块链项目定制开发


qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 小Q正在给一条长度为n的道路设计路灯安置方案。 为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用’.’表示, 不需要照亮的障碍物格子用’X’表示。 小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos – 1, pos, pos + 1这三个位置。 小Q希望能安置尽量少的路灯照亮所有’.’区域, 希望你能帮他计算一下最少需要多少盏路灯。