首页 > 试题广场 >

安置路灯

[编程题]安置路灯
  • 热度指数:43874 时间限制: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

算法思路

遍历路灯字符串,遇见“.”,就给计数器+1,然后往后挪三个位置。如果遇到“X”,就直接往后挪一个位置。

编程思路

路灯个数放入数组n中,路灯对应的字符串放入数组lantern中,要放路灯的个数放入lantern_count中。这三个数组是一一对应的。双重循环来遍历lantern中的字符串,如果遇到“.”,对应的lantern_count+=1,j+=3(挪三个位置)。如果遇到“X”,j+=1(挪一个位置)。

if __name__ == '__main__':
    count = int(input())  # 测试用例的个数
    n = []
    lantern = []
    for i in range(count):
        n_tmp = int(input())  # 路灯个数
        n.append(n_tmp)
        lantern_tmp = input()  # 路灯分布字符串
        lantern.append(lantern_tmp)
    lantern_count = [0 for i in range(count)]  # 存储最终结果的数组
    for i in range(len(lantern)):  # 循环路灯数
        j = 0
        while (j < len(lantern[i])):  # 循环对应路灯排列字符串
            if lantern[i][j] == '.':
                j += 3
                lantern_count[i] += 1
            else:
                j += 1
    print(lantern_count[0])
    for i in range(len(lantern_count) - 1):
        print(lantern_count[i + 1])
编辑于 2018-03-28 11:00:58 回复(25)
#include <bits/stdc++.h>
using namespace std;
int main() {
    int m; cin >> m;
    while (m--) {
        int n; cin >> n; string s; cin >> s;
        int ans = 0;
        for (int i=0; i<s.length(); i++) {
            if (s[i] == '.') {
                i+=2;
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

发表于 2019-07-30 01:52:19 回复(5)

本套8道题全部pass的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)
牛客网上的其他题目解答也在持续更新。

#include <iostream>
using namespace std;
int main()
{
    int t; cin >> t;
    for (int i = 0; i < t; i++) {
        int n; cin >> n;
        int j = 0, count = 0;
        while (j++ < n) {
            char ch; cin >> ch;
            if (ch == '.') {
                count++;
                if (j++ < n) cin >> ch;
                if (j++ < n) cin >> ch;
            }
        }
        cout << count << endl;
    }
    return 0;
}
发表于 2018-03-28 19:13:28 回复(2)
发表于 2018-03-30 15:09:35 回复(8)
t = int(input())
for i in range(t):
    n = int(input())
    s = input()
    ans = 0
    j = 0
    while j < n:
        if s[j] == '.':
            ans += 1
            j += 3
        else:
            j += 1
    print(ans)

发表于 2019-06-22 18:29:18 回复(3)
可以用贪心的思想,推导过程如下,从前往后遍历,遇上'.'则放置路灯。
  1. 遇上了'.',如果在当前'.'放置路灯,那么能照到当前和下一个(因为我们是从头开始遍历,在遍历到这个'.'之前都已经被照亮了)。如果在下一个位置放灯,那么能照亮当前位置和后两个,所以一定是在下一个位置放灯照亮的最多。
  2. 最后考虑一下遍历到末尾的边界情况。
  3. 遇上‘X’不考虑
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t > 0) {
            t--;
            int n = sc.nextInt();
            String s = sc.next();
            int sum = 0;
            char[] c = s.toCharArray();
            for (int i = 0; i < n; i++) {
                if (c[i] == '.') {
                    if (i + 2 < n) {
                        c[i] = 'X';
                        c[i + 1] = 'X';
                        c[i + 2] = 'X';
                        sum++;
                    } else if (i + 1 == n - 1) {
                        c[i] = 'X';
                        c[i + 1] = 'X';
                        sum++;
                    } else if (i == n - 1) {
                        c[i] = 'X';
                        sum++;
                    }
                }
            }
            System.out.println(sum);
        }

    }
}


发表于 2019-08-11 11:54:34 回复(0)
这道题的思路是贪心,我们从左往右枚举每个位置,如果一个位置没有被照亮但是又需要被照亮('.'),那么就从这个位置开始的连续3个格子都设为‘X’,并且路灯数+1。直到把整段路考虑完。
#include <iostream>
#include <algorithm>
using namespace std;
char s[1005];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cin>>s;
        int ans=0;
        for(int i=0;i<n;++i)
            if(s[i]=='.')
            {
                int cnt=0;
                for(int j=i;j<n;++j)
                    if(s[j]=='X')
                        break;
                    else cnt++;
                int res=(cnt+2)/3;
                ans+=res;
                for(int j=i;j<i+res*3&&j<n;++j)
                    s[j]='X';
            }
        cout<<ans<<endl;

    }
}
发表于 2018-03-28 01:53:16 回复(0)
import java.util.*;
//贪心算法求解:1.当遇到第一个'.'时,表示该位置需要被照亮,此时不安装路灯,在它的下一个位置安装路灯,即sum+1;
//因为该路灯位置的下一个位置已经被照亮了,因此下标+2
//遇到‘X’时跳过,因为不需要安装
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int i = 0; i < t; i++){
            int n = sc.nextInt();
            String s = sc.next();
            int sum = 0;
            for(int j = 0; j < n; j++){
                if(s.charAt(j) == '.'){
                    sum++;
                    j = j + 2;
                }
            }
            System.out.println(sum);
        }
    }
}

发表于 2019-09-02 15:20:07 回复(1)
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        bool flag = true;
        cin>>n;
        string str;
        cin>>str;
        int count = 0;  //方格的数量
        int lampcount = 0;  //路灯数量
        for(int i=0;i<n;i++)
        {
            if(flag==true && str[i]=='X')  //开头是X,就可以略过
                continue;
            if(flag==false && str[i]=='X')  //X不在开头,那就要把它当作要照亮的区域
            {
                count++;
            }
            if(str[i] == '.')  //在一开始的时候加上路灯,之后就不需要判断
            {
                count++;
                if(true == flag)
                lampcount++;
                flag = false;
            }
            if(3 == count)  //满3格清0
            {
                count = 0;
                flag = true;
            }           
        }
         cout<<lampcount<<endl;
    }
}

发表于 2019-09-16 10:55:05 回复(0)
"""
一盏路灯照亮3个格子
当遇到'.'且cnt3为0,ans计数,点亮一盏路灯flag
当'X'且当前没有路灯是cnt3保持0,其他情况cnt3自增1
当超过3格,flag、cnt3重置
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open('input.txt', 'r')
    t = int(input().strip())
    while t:
        n = int(input().strip())
        s = input().strip()
        ans, flag, cnt3 = 0, 0, 0
        for i in range(len(s)):
            if s[i] == '.':
                if cnt3 == 0:
                    flag = 1
                    ans += 1
                cnt3 += 1
            elif flag == 1:
                cnt3 += 1
            if cnt3 == 3:
                flag = 0
                cnt3 = 0
        print(ans)
        t -= 1

发表于 2019-07-02 11:52:15 回复(0)
import java.util.Scanner;

/*
 * 有点类似智力题
 * */
public class LayLamp {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            while (n-- > 0) {
                int len = scanner.nextInt();
                String line = scanner.next();
                int count = 0;
//                在需要防止路灯位置的右边放置路灯
                for (int i = 0; i < len; i++) {
                    if (line.charAt(i) == 'X') {
                        continue;
                    }
                    count++;
                    i += 2;
                }
                System.out.println(count);
            }
        }
    }
}
发表于 2018-03-28 13:09:19 回复(4)
WAK头像 WAK
#include<iostream>
#include<string>
usingnamespacestd;
intmain(){
    intt;
    while(cin>>t){
        for(inti =0;i<t;i++){
            intn;
            string str;
            cin>>n>>str;
         
            intnum=0;
            for(inti = 0;i<str.size();){
                if(str[i]=='.'){
                    num++;
                    i+=3;
                }
                else
                    i++;
            }
            cout<<num<<endl;
        }
    }
    system("pause");
    return0;
}

发表于 2018-03-28 11:42:24 回复(0)
本题主要思路就是,能不照到障碍物就不照到障碍物,所以有两种情况:
1、当遇到障碍物'X'时,就直接往后遍历;
2、当遇到'.'时,不管后面的点是'X'还是'.',直接以后面那个点为中心,照亮前后两个点,然后继续便利三个点后面的点;
比如: ABCEFG   六个点紧挨着,A是'.',则直接以B为中心,照亮A和C两个点,然后继续遍历  EFG

因为不管A后面是'X'还是'.',都至少需要消耗一个灯来照亮A。
发表于 2020-03-15 17:25:01 回复(0)
大家可以百度一下计算机网络技术中的“窗口滑动”技术,这个题解就是根据那个思路来解题的。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    /**
     * 窗口宽度
     */
    private static final int WIN_WIDTH = 3;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int times = Integer.valueOf(br.readLine());
        String roadStr;
        char[] roads = null;
        for (int time = 0; time < times; time++) {
            br.readLine();
            roadStr = br.readLine();
            // 道路队列
            roads = roadStr.toCharArray();
            int sum = 0;
            for (int i = 0; i < roads.length;) {
                if (roads[i]=='.'){
                    ++sum;
                    i+=3;
                }else {
                    i++;
                }
 
            }
            System.out.println(sum);
        }
 
    }
    /**
     * 思路:
     *  窗口滑动,窗口宽度为3,一个一个向右扫描、,当窗口最左侧是需要被照亮的时候,就加一盏灯。
     *  每次点灯以后,想右滑动3个距离
     */
}


发表于 2020-03-15 15:30:23 回复(0)
for i in range(int(input())):
    b,c,j,p = int(input()),input(),0,0
    while j < b:
        if c[j] == '.':
            p,j = p + 1,j + 2
        j += 1
    print(p)

发表于 2020-03-15 11:29:50 回复(0)
# 一盏路灯可以照亮当前位置和相邻位置
# 首先,假设没有障碍物,则x个位置需要最少多少盏路灯⌈x/3⌉,即x除以三向上取整
# 现在中间夹杂着一些不需要照亮的位置,这些位置不是必须照亮,但是可以被照亮,也可以安置路灯
# 从左向右,贪心算法,第一盏灯最多照亮3个位置(不管需不需要被照亮),除非位置不够
# 前面的位置都被遍历过了,当前位置是'X'不需要照亮就跳过,寻找下一个'.'

n = int(input())
target = []
for i in range(n):
    length = int(input())
    s = input()
    j, result = 0, 0
    while j < length:
        if s[j] == '.':
            result += 1
            j += 3
        else:
            j += 1
    target.append(result)
for e in target:
    print(e)
写代码之前,先把思路写下来有助于思考和少犯错误
编辑于 2020-03-06 21:43:58 回复(0)
JavaScript(Node)😎 题目:网易-安置路灯
// jsnode多行输入输出
//遍历路灯字符串'.'=>cnt++ i+=3 'X'=>i++
// return cnt
const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = [],t
rl.on('line',line=>{
    if(!line) return
    inArr.push(line.trim())
    if(inArr.length === 1){
        t = +inArr[0]     
    }
    if(inArr.length === 1+2*t){
        for (let i = 0; i < t; i++) {
            const n = +inArr[i*2+1]
            const roads = inArr[i*2+2].split('')
            console.log(needLamp(n,roads))
        }
    }
    function needLamp(n ,roads) {
        let cnt = 0
        let i = 0
        while (i<n) {
            if(roads[i]==='.'){
                cnt++
                i+=3
            }else{
                i++
            }
        }
        return cnt
    }
})


发表于 2020-02-25 17:56:12 回复(0)
首先我们需要判断当前的字符串是否包含'.'(是否需要安装灯)
用str.contains(".")判断是否包含'.', 如果不包含则说明这段路不需要安装灯,所以输出结果为零,
如果包含'.',说明需要安装路灯
思路如下:
首先判断str.charAt(j)是否等于 '.' ,如果结果为真,我们需要安装的路灯数目+1,j+2;(j+2意思是直接跳到j后面的第三个路段,因为只要str.charAt(j)=='.'成立,我们只需要把路灯安装在 j+1的位置,这样能照亮j ,j+1,j+2这三个位置,所以不需要考虑j+1和j+2的情况)
代码如下
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin = new Scanner(System.in);
		int n = cin.nextInt();
		
		for (int i = 0; i < n; i++) {
			int out = 0;//需要的路灯数目
			int m = cin.nextInt();
			String str = cin.next();
			if(str.contains(".")) {
				if(m<=3) {
					out=1;
					System.out.println(out);
				}
				else if(m>3) {
					for(int j=0;j<m;j++) {
						if(j==0) {
							if(str.charAt(j)=='.') {
								out++;
								j=j+2;
							}
							else continue;
						}
						else if(j==m-2) {
							if(str.charAt(j)=='.' || str.charAt(j+1)=='.') {
								out++;
								
							}
							break;
							
						}
						else if(j==m-1 ) {
							if(str.charAt(j)=='.') {
								out++;
								
							}
							break;
						}
						else {
							if(str.charAt(j)=='.') {
								out++;
								j=j+2;
							}
							else continue;
							
						}
					}
					System.out.println(out);
				}
			}
			else System.out.println(0);
		}

	}

}

发表于 2019-11-01 16:10:23 回复(1)
import java.util.Scanner;
public class Main {
    //思路:小贪心,假如第一个遇到`.`反正都要花费一个灯来照亮,所以就把这个灯安装到下一个位置
    //然后来到第4个格子,同时也说明新来到的格子不能依靠前面的灯来把自己照亮
    public static int light(String road) {
        if(road == null || road.length() == 0) {
            return 0;
        }
        int n = road.length();
        int ans = 0;
        //for循环中的变量i:
        //若遇到'.'则向后移3位,
        //若遇到'X'则向后移1位
        for(int i = 0; i < n; i++) {
            if(road.charAt(i) == '.') {
                ans++;
                i += 2;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = Integer.valueOf(s.nextLine());
        for(int i = 0; i < n; i++) {
            s.nextLine();
            System.out.println(light(s.nextLine()));
        }
    }
}
发表于 2019-09-22 10:05:17 回复(0)
import sys
n=int(sys.stdin.readline().strip())
list1=[]
list2=[]
for i in range(n):
    list1.append(int(sys.stdin.readline().strip()))
    list2.append(str(sys.stdin.readline().strip()))
for i in range(n):
    count=0
    j=0
    ll=list(list2[i])
    while(j<list1[i]):
        if ll[j]=='.':
            j+=3
            count+=1
        else:
            j+=1
    print(count)
发表于 2019-08-27 15:36:19 回复(0)