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

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

本套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 回复(5)
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)
#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个格子都设为‘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<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)
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 回复(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)
"""
一盏路灯照亮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)
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)
解题思想:让一个路灯去照亮更多的地方,当发现一个需要照亮的地方就在它的下一个位置安置一个路灯(贪心算法)。
#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)
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)

热门推荐

通过挑战的用户

查看代码