首页 > 试题广场 >

安置路灯

[编程题]安置路灯
  • 热度指数:333 时间限制: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"就跳过一个格子,遇到"."就安装灯,由于一个灯可以管三个位置的照明,所以安装完灯之后往后跳3格(灯安装在下一个位置,坑点:“X”上可以安装灯)。宗旨就是不走回头路,每来到一个位置,说明该位置之前的所有该照亮的地方已经照亮了。
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while(t-- > 0){
            int n = Integer.parseInt(br.readLine());
            char[] road = br.readLine().toCharArray();
            int count = 0;
            for(int i = 0; i < n; ){
                if(road[i] == 'X'){
                    i++;
                }else{
                    if(i < n - 1){
                        count++;
                        i += 3;
                    }else{
                        if(road[i] == '.'){
                            count++;
                        }
                        i++;
                    }
                }
            }
            System.out.println(count);
        }
    }
}

发表于 2022-03-18 12:20:02 回复(0)
奇怪 为啥X的位置可以放灯啊
发表于 2022-07-28 09:58:55 回复(0)
import math
instance_num = int(input())
for _ in range(instance_num):
    length = int(input())
    instance = (input()).strip()

    charlist = instance.split('X')
    ans = sum([math.ceil(len(x)/3for x in charlist])

    print(min((math.ceil(length/3),ans)))
发表于 2020-04-01 16:42:21 回复(0)
java:
    public static void main(String[] args){
        // 只用关注不能被整除的地方
        //剩下一个可以和下下个需要照亮的地方共用一个 因为不论如何这个灯泡都要拿出来
        // 如果剩下超过两个就不存在公用的情况 这个灯泡必然要先加上 再处理后面的
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int m;
            for (int i = 0; i < n; i++) {
                m = in.nextInt();
                int continue_black = 0;
                String road = in.next();
                int bulbs = 0;
                for (int j = 0; j < m; j++) {
                    if(road.charAt(j) == '.' || continue_black % 3 == 1){  //  给X一次纳入考虑机会
                        continue_black ++;
                    }else{
                        bulbs += continue_black / 3;
                        if(continue_black % 3 != 0){
                            bulbs ++;
                        }
                        continue_black = 0;
                    }
                }
                bulbs += continue_black / 3;
                if(continue_black % 3 != 0) {
                    bulbs++;
                }
                System.out.println(bulbs);
            }
        }
    }
python:
    while True:
        n = int(input().strip())  # 测试用例
        for i in range(n):
            road_len = int(input().strip())
            road_signal = input().strip()
            light_count = 0
            black_continue_count = 0
            for j in range(road_len):
                if road_signal[j] == "." or black_continue_count % 3 == 1:  # 给X一次纳入考虑的机会
                    black_continue_count += 1
                else:
                    light_count += black_continue_count // 3
                    light_count += 0 if black_continue_count % 3 == 0 else 1
                    black_continue_count = 0
            light_count += black_continue_count // 3
            light_count += 0 if black_continue_count % 3 == 0 else 1
            print(light_count)



发表于 2019-08-08 18:04:48 回复(0)
将字符串根据 X 分割成无数个list。
求解每个
 int ( ( list的长度 + 2 ) / 3)
并将这些正整数加起来就是答案了
发表于 2019-08-07 09:49:15 回复(0)
t =int(input())
for_ inrange(t):
    n =int(input())
    s =input()
    if(n <=3and'.'ins):
        print(1)
    else:
        flag =[]
        forc ins:
            if(c =='X'):
                flag.append(0)
            else:
                flag.append(1)
        count =0
        fori inrange(1, n-1):
            if(flag[i-1] ==1):
                count +=1
                flag[i-1] =0
                flag[i] =0
                flag[i+1] =0
            if(i ==n -2and(flag[n-1] ==1orflag[n-2] ==1)):
                count +=1
        print(count)
发表于 2019-08-03 14:22:36 回复(0)