首页 > 试题广场 > 安置路灯
[编程题]安置路灯

小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 回复(8)

本套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 回复(3)
#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 回复(3)
"""
一盏路灯照亮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)
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 回复(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)
这道题的思路是贪心,我们从左往右枚举每个位置,如果一个位置没有被照亮但是又需要被照亮('.'),那么就从这个位置开始的连续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)
解题思想:让一个路灯去照亮更多的地方,当发现一个需要照亮的地方就在它的下一个位置安置一个路灯(贪心算法)。
#include<iostream>
#include<string>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        string s;
        cin >> s;
        int m = 0;
        for(int i = 0; i < n; i++){
            if(s[i] == '.'){
                ++m;
                i += 2;
            }
        }
        cout << m << endl;
    }
}


编辑于 2019-08-14 21:57:14 回复(0)
可以用贪心的思想,推导过程如下,从前往后遍历,遇上'.'则放置路灯。
  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)
Java解法:找到规律,碰到第一个‘.’就往后走两位。
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        for (int i=0;i<t;i++){
            int num = input.nextInt();
            String s = input.next();
            int count = 0;
            for (int j=0;j<num;j++){
                if (s.charAt(j)=='.'){
                    count++;
                    j = j+2;
                }
            }
            System.out.println(count);
        }
    }
}

发表于 2019-08-04 19:58:23 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        string s;
        cin>>s;
        int cnt = 0;
        for(int i=0;i<n;i++){
            if(s[i]=='.'){
                cnt++;
                i += 2;
            }            
        }
        cout<<cnt<<endl;
    }
    return 0;
}

发表于 2019-07-11 07:54:51 回复(0)
import sys
lines = sys.stdin.readlines()
exam_nums = int(lines[0].strip())
if 1<=exam_nums<=1000:
    for i in range(1, 2*exam_nums, 2):
        n = int(lines[i].strip())
        s = lines[i+1].strip()
        j = 0
        count = 0
        while j<n:
            if s[j] == '.':
                count += 1
                j += 3
            elif s[j] == 'X':
                j += 1
        print(count)
else:
    print(0)

遇到.计数,加3,遇到X加1
发表于 2019-07-06 19:54:02 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t,n;
    string s;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        cin>>n;
        cin>>s;
        int cont=0;
        for(int j=0;j<n;j++)
        {
            if(s[j]=='X')
                continue;
            else
            {
                j=j+2;
                cont++;
            }
        }
        cout<<cont<<endl;
    }
    return 0;
}

发表于 2019-06-28 20:36:33 回复(0)
/*
灯居然可以放在障碍物上。
*/
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while (T-- > 0) {
            int n = in.nextInt();
            String s = in.next();
            int ans = 0;
            int tmp = 0;
            for (int i = 0; i < n; i++) {
                if (s.charAt(i) == '.') {
                    ans++;
                    i += 2;
                }
            }
            System.out.println(ans);
        }
    }
}

发表于 2019-06-26 10:05:09 回复(0)

思路与skyamz一样:遇见“.”,就给计数器+1,然后往后挪三个位置。如果遇到“X”,就直接往后挪一个位置。

#include <iostream>
#include <string>
using namespace std;
int main()
{
    int testNum=0;
    cin>>testNum;
    for(int i=0; i < testNum; i++)
    {
        int lightNum=0;
        int length=0;
        cin>>length;
        if(length<=0)
        {
            cout<<0<<endl;
            continue;
        }       
        string str;
        cin>>str;
        for(int i=0; i < length;i++)
        {
            if(str[i]=='X')
            {
                continue;
            }
            // so str[i]='.'
            lightNum++;
            i+=2;
        }
        cout<<lightNum<<endl;
    }
}
发表于 2018-04-18 23:01:59 回复(0)
python3,正则匹配法,从头开始找“.”,并找从找到的"."中往后延迟2个数,组成一组(3个),这一组就花费了一个电灯,对剩下的包含"."在进行一次判断。代码如下,如有问题可以私聊我。
import math
import re
num=int(input('') )
total_list = []
temp_list=[]
for i in range(num):  
    a = input()  
#    temp_list.append(a) 
    b = input()
    temp_list.append(b)  
  
for rount in temp_list:
    pipei = r'\...'
    re_li = re.findall(pipei, rount) 
    add_li= re.sub(pipei,'', rount) 
    if add_li.find('.')!=-1:
        print(len(re_li)+1)
    else:
        print(len(re_li))

发表于 2018-04-15 18:58:00 回复(2)
    
def GetLaternNum(street):
    street_len=len(street)

    laternNum=0
    i=0
    while(i<street_len):
        if(street[i]=='.'):
            laternNum+=1;
            i+=3;
        else:
            i+=1;

    return laternNum


TestNum=int(input())

for i in range(TestNum):
    streen_len=int(input())
    street=input()
        
    print(GetLaternNum(street))

发表于 2018-04-05 14:22:12 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    for(cin>>N;N--;)
    {
        int n,ans=0;
        string road;
        cin>>n>>road;
        for(int i=0;i<n;)
        {
            for(;i<n&&road[i]=='X';++i){}
            for(;i<n&&road[i]=='.';++ans,i+=3){}
        }
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2018-03-31 09:21:31 回复(2)

热门推荐

通过挑战的用户

查看代码