小Q正在给一条长度为n的道路设计路灯安置方案。
为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用'.'表示, 不需要照亮的格子用'X'表示。
小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。
小Q希望能安置尽量少的路灯照亮所有'.'区域, 希望你能帮他计算一下最少需要多少盏路灯。
小Q正在给一条长度为n的道路设计路灯安置方案。
为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用'.'表示, 不需要照亮的格子用'X'表示。
小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。
小Q希望能安置尽量少的路灯照亮所有'.'区域, 希望你能帮他计算一下最少需要多少盏路灯。
输入的第一行包含一个正整数t(1 <= t <= 1000), 表示测试用例数
接下来每两行一个测试数据, 第一行一个正整数n(1 <= n <= 1000),表示道路的长度。
第二行一个字符串s表示道路的构造,只包含'.'和'X'。
对于每个测试用例, 输出一个正整数表示最少需要多少盏路灯。
2 3 .X. 11 ...XX....XX
1 3
#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
#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的情况
# 思路:使用贪心的思想,每遇到一个'.',就把接下来两位都置为'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]))
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; }
答案全在Find函数里。其实就是一个递归,上面几个都是出递归的条件,写的有点乱,有兴趣的可以帮我整理一下
#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;}elsei++;}cout<<num<<endl;}}system("pause");return0;}