Codeforces 861C(贪心)

Codeforces 854C
题意:给你一个字符串,现在要你给其中加空格隔开单词,使得每个单词不能有连续三个以上不同的辅音字母,输出加的空格最少的字符串。

我们可以考虑贪心。如果出现3个连续的辅音并且这些辅音之中有至少两个不同,那么就在这3个数中的第二第三个数中断开。这样是最优的。这样使得后面一段的辅音数最小,自然后面的错误会更少

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
char s[3000 + 5];
int n;
void clean() {
}
void solve() {
clean();
int lx = 0, df = 0;
n = strlen(s + 1);
for (int i = 1; i <= n; i++) {
if (s[i] != 'a' && s[i] != 'e' && s[i] != 'i' && s[i] != 'o' && s[i] != 'u') {
lx++; if (s[i] != s[i - 1]) df++;
} else lx = 0, df = 0;
if (lx < 3) putchar(s[i]); else {
if (df >= 2) putchar(' '), putchar(s[i]), lx = 1, df = 1; else putchar(s[i]);
}
}
}
int main() {
scanf("%s", s + 1), solve();
return 0;
}

------ 本文结束 ------