安置路灯

方法：
　　贪心

想法：
　　对于一个没被照亮的点来说，最好是只占用路灯能照亮的区域的最左边，这样的话，能够最大化利用路灯的照亮区域，这种安装方式满足了两个要求，一是所有的路灯都被覆盖到了，只要当前位置没有被路灯覆盖，就立即安装路灯，二是最大程度减少了使用路灯的数量，没有浪费掉路灯能照亮的左侧区域，并且最好情况下能同时覆盖三个需要被照亮的点。

算法：
　　遍历一条路的同时维护两个变量，当前路灯能照亮的最远距离max_，当前已使用的路灯数量cnt，如果遇到的是'.'，并且它还没有被照亮，说明此时不得不安装路灯，让cnt++，同时将路灯所能照亮的最远距离max_更新为当前位置+2。

复杂度分析：
　　时间复杂度：O(N)，其中 N 是路灯长度，一次遍历。
　　空间复杂度：O(1)，max_和cnt，常数的空间。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n;
    string road;
    for(int i=0;i<n;i++)
    {
        cin>>m>>road;
        int cnt=0,max_=-1;
        for(int j=0;j<m;j++)
            if(road[j]=='.'&&j>max_)
            {
                cnt++;
                max_=j+2;
            }
        cout<<cnt<<endl;
    }
    return 0;
}