首页 > 试题广场 >

安置路灯

[编程题]安置路灯
  • 热度指数:45 时间限制: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
#include<vector>
#include<iostream>
#include<string>
using namespace std;

int transRoad(string s){
    int count =0;
    for(auto i=s.begin();i!=s.end();i++){
        if(*i=='.'){
            count++;
            *i='X';
            if(i+1!=s.end())*(i+1)='X';
            else break;
            if(i+2!=s.end())*(i+2)='X';
            else break;
        }
    }
    return count;
}

int main(){
    vector<int>res;
    int t,n;
    string road;
    cin>>t;
    while(t--){
        cin>>n;
        cin>>road;
        res.emplace_back(transRoad(road.substr(0,n))) ;
    }
    for(auto i:res){
        cout<<i<<"\n";
    }
    return 0;
}

发表于 2021-04-16 10:58:00 回复(0)
如果障碍物可以放路灯,则每遇到一个". "就跳2格
发表于 2021-04-14 19:09:20 回复(0)