安置路灯
安置路灯
http://www.nowcoder.com/questionTerminal/3a3577b9d3294fb7845b96a9cd2e099c
题目难度：二星
考察点：贪心
分析：
对于这道题来说，如果在第i个位置上安装路灯，那么它能够照亮的地方就是i-1, i和i+1,那么安装路灯最少的方法就是在三个位置的中间设置路灯，即如果第i个位置为'.'， 那么显然在 i+1 处安装路灯是最好的，它可以照到位置i, i+1和i+2，这样能够最大程度的减少路灯的数目。
例如下图：
算法实现：
(1) 设置遍历指针i=0;
(2) 如果第i个位置为'.'，ans++（在i+1处放置路灯，可以照亮i, i+1, i+2），然后从第i+3位置处继续遍历，即i=i+3；
(3) 如果第i个位置为'x'，那么指针i++。
(4) 一直遍历字符串末尾结束，最后输出ans即可。复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)代码：
#include <bits/stdc++.h> using namespace std; int main() { int T; cin>>T; while(T--) { int n; cin>>n; string s; cin>>s; int len = s.size(), i = 0, ans = 0; while(i < len) { if(s[i] == '.') { ans++; i = i+3; } else i++; } cout<<ans<<endl; } return 0; }
