首页 > 试题广场 >

安置路灯

[编程题]安置路灯

热度指数：1596 时间限制：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

算法知识视频讲解

SGHのRY

#include <iostream>
#include <string>
using namespace std;
int main()
{
    int size;
    cin >> size;
    int len;
    while (cin >> len)
    {
        string str;
        cin >> str;

        int count = 0;
        for(int i = 0; i < len; i ++)
        {
            if(str[i] == '.')
            {
                i = i + 2 ;
                count ++;
            }
        }

        cout << count << endl;
    }

    return 0;
}
 //贪心，每有一个‘.’则安置一个路灯再向后移两位~~~~By SGHRY

发表于 2018-06-02 13:20:29 回复(3)

v特仑苏v

#include <cstdio>
#include <cstring>

int num, length;
char road[1003];
int result[1000];
char* p;
int i;

int main()
{
    scanf("%d", &num);
    for (i = 0; i < num; ++i) {
        scanf("%d", &length);
        scanf("%s", road);
        //road[length + 2 - length%3] = '\0';
        p = road;
        while (*p != '\0') {
            if (*p == 'X')
                ++p;
            else {
                ++result[i];
                p += 3;
            }
        }
        memset(road, 0, length + 3);
    }
    for (i = 0; i < num; ++i)
        printf("%d\n", result[i]);
}

一次看3格共8种情况
...
..X
.XX
.X.
上述4种直接一个路灯搞定再跳3格看下一组
X.X
XX.
XXX
X..
上述4种路障开头直接舍弃X再移位直至变成1-4的情况

发表于 2018-08-11 10:06:25 回复(0)

C/C++

倚杖听江声

#include <stdio.h>
#include "iostream"
#include "fstream"
#include "vector"
using namespace std;

int update_donemark(int done_mark, char* str,int size)//局部最优求解
{
    int choose1 = 1;
    int choose2 = 1;
    if (done_mark+1<size&&str[done_mark + 1] == '.')
    {
        choose1++;
        choose2++;
    }
    if (done_mark + 2<size&&str[done_mark + 2] == '.')
    {
        choose2++;
    }
    if (choose1 > choose2)
    {
        return done_mark + 2;
    }
    else return done_mark + 3;
}
int func(int size, char* str)
{
    int done_mark = 0;//贪心算法已经贪吃掉str[done_mark]之前的所有区域
    int count = 0;
    while (done_mark < size)
    {
        while (str[done_mark] == 'X')
        {
            done_mark++;
        }
        if (done_mark < size)
        {
            done_mark = update_donemark(done_mark, str,size);
            count++;
        }
        else break;
    }
    return count;
}

int main()
{
////////////输入操作部分/////////////////////
    //fstream fin("7.txt");
    int test_num = 0;
    cin >> test_num;
    vector<pair<int, char*>> vec;
    for (int i = 0; i < test_num; i++)
    {
        int size = 0;
        char* temp = new char[1001];
        cin >> size >> temp;
        pair<int, char*> data(size, temp);
        vec.push_back(data);
    }

////////////输出操作部分/////////////////////
    for (int i = 0; i < test_num; i++)
    {
        cout << func(vec[i].first, vec[i].second)<<endl;
    }

    return 0;
}

发表于 2018-07-27 10:39:16 回复(0)

最爱菠萝味

# 思路：使用贪心的思想，每遇到一个'.'，就把接下来两位都置为'x'。
# 输入数据
test_num = input()
input_list = []
for i in range(2*int(test_num)):
    input_list.append(input())

def latern_min(route_list):
    count = 0
    route_list = list(route_list)
    for i in range(len(route_list)):
        if route_list[i] is '.':
            try:
                route_list[i+1] = 'x'
                route_list[i+2] = 'x'
                count += 1
            except IndexError:
                count += 1
    return count

for i in range(0, len(input_list), 2):
    print(latern_min(input_list[i+1]))

发表于 2018-06-15 15:42:48 回复(0)

牛客193259817号

 public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        scanner.nextLine();
        String[] strings=new String[n];
        int[] lens=new int[n];
        int[] res=new int[n];
        for (int i = 0; i < n; i++) {
            lens[i]=scanner.nextInt();
            scanner.nextLine();
            strings[i]=scanner.nextLine();
        }
        for (int i = 0; i < n; i++) {
            res[i]=minLight(strings[i]);
        }
        for (int re : res) {
            System.out.println(re);
        }

    }

    public static int minLight(String s){
        if(s==null || s.length()==0)return 0;
        int res=0;
        int index=0;
        char[] chars = s.toCharArray();
        while(index<chars.length){
            if(chars[index]=='X'){
                index++;
            }else{
                res++;
                if(index+1==s.length())break;
                else {
                    index=index+3;
                }
            }
        }
        return res;
    }

发表于 2022-05-23 15:18:50 回复(0)

从那天开始

".X."为什么是一个？不应该在有点的地方放入一个路灯，一共是两个吗？

发表于 2020-08-19 01:28:59 回复(0)

牛客8751634号

只需要考虑连续三个点，剩余一两点分别考虑

#include <iostream>

#include <string>
#include <vector>
using namespace std;
int main()
{
int t;
while (cin >> t) {
vector<int> out;
for (int i = 0; i < t; ++i) {
int tmp;
string str;
cin >> tmp >> str;

int cur = 0;
int dot = 0, cnt = 0, res = 0;
while (cur < tmp) {
while (cur < tmp&&str[cur] == '.') {
++dot; ++cur;
}
cnt += dot / 3;
res = dot % 3;
if (res == 1) {
cur += 2;
++cnt;
}
else if (res == 2) {
cur += 1;
++cnt;
}
while (cur < tmp&&str[cur] == 'X')
++cur;
dot = 0;
}
out.push_back(cnt);
}
for(int i = 0;i<t;++i)
cout << out[i] <<endl;
}
return 0;
}

编辑于 2018-07-02 20:46:25 回复(0)

sghwn2019

#include <stdio.h>

int Find(char *a,int len)
{
if (len <= 0)
        return 0;
    if(len<=3&&*a!='X')
        return 1;
    if(*a=='X')
        return Find(a+1,len-1);
    if(*(a+1)=='X'&&*(a+2)!='.')
        return 1+Find(a+2,len-2);
    return 1+Find(a+3,len-3);
}

int main()
{
    int times;
    scanf("%d",&times);
    int result[times];
    for(int i=0;i<times;++i)
    {
        int len;
        scanf("%d",&len);
        char a[len+1];
        scanf("%s", a);

        result[i]=Find(a,len);
    }

    for(int i=0;i<times;++i)
        printf("%d\n",result[i]);
    return 0;
}

答案全在Find函数里。其实就是一个递归，上面几个都是出递归的条件，写的有点乱，有兴趣的可以帮我整理一下

发表于 2018-06-11 21:55:24 回复(0)

柒七七七七七七

class Solution { public: int quantity(int m,string ch) 
{  int ptr=0;  int sum=0;  while(ptr<m)
    { if(ch[ptr]=='.')
            {
                sum++;
                ptr=ptr+3;
            } else if(ch[ptr]=='X')
            {
                ptr++;
            }
        } return sum;
    }
};

编辑于 2018-06-08 16:13:27 回复(0)

winnereven

#include<iostream>

using namespace std;
int main()
{
    int testnum;
    int roadlength;
    int lightnum=0;
    char roadstu[1010];
    cin>>testnum;
    for(int i=0;i<testnum;i++)
    {
        cin>>roadlength;
        cin>>roadstu;
        for(int j=0;j<roadlength||roadstu[j]!='\0';j++)
        {
            if(roadstu[j]=='.')
            {
                lightnum++;
                j+=2;
            }
        }
        cout<<lightnum<<endl;
        lightnum=0;
    }
    return 0;
}

发表于 2018-06-01 16:49:00 回复(0)

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;



	}