hihocoder offer收割编程练习赛11 A hiho字符串

思路:

我用的尺取。

注意题目描述为恰好2个'h',1个'i',1个'o'。

实现:

 #include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std; const int INF = 0x3f3f3f3f; int ch[], ci[], co[]; bool check(int pos, int a, int b, int c)
{
return ch[pos] <= a - && ci[pos] <= b - && co[pos] <= c - ;
} int main()
{
string s;
cin >> s;
int n = s.length();
ch[] += (s[] == 'h');
ci[] += (s[] == 'i');
co[] += (s[] == 'o');
int last = , min_len = INF;
for (int i = ; i < n; i++)
{
ch[i] = ch[i - ] + (s[i] == 'h');
ci[i] = ci[i - ] + (s[i] == 'i');
co[i] = co[i - ] + (s[i] == 'o');
if (ch[i] >= && ci[i] >= && co[i] >= )
{
while (last < i && check(last, ch[i], ci[i], co[i]))
{
last++;
}
if (ch[i] - ch[last - ] == &&
ci[i] - ci[last - ] == &&
co[i] - co[last - ] == )
min_len = min(min_len, i - last + );
}
}
if (min_len != INF)
cout << min_len << endl;
else
cout << - << endl;
return ;
}
上一篇:Wannafly 挑战赛 19 参考题解


下一篇:HDU 6185 Covering 矩阵快速幂