安置路灯——贪心,简单易懂
安置路灯
http://www.nowcoder.com/questionTerminal/3a3577b9d3294fb7845b96a9cd2e099c
贪心算法即可,因为每个点都必须要被照亮。所以从前向后每找到一个s[i]位置为 . ,则将灯放置在i+1位置会有最好的效果,这样i、i+1和i+2都会被照亮,X位置不需要照亮,但是也可以被照亮,哈哈
#include <string> #include <iostream> using namespace std; int main() { int t; cin>>t; string s; while(t--) { int n; cin>>n; s=""; getchar(); getline(cin,s); int count=0; for(int i=0;i<s.length();i++) { if(s[i]=='X') continue; count++; s[i]='X'; i+=2; } cout<<count<<endl; } return 0; }