链接:https://ac.nowcoder.com/acm/contest/27302/C
来源:牛客网
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
一天Phenix得到了一个长度为nn的字符串,字符串仅由大写字母A~Z组成,现在Phenix想知道最少需要删除多少个字符使字符串变成NEUQNEUQ……这种由若干个"NEUQ"组成的形式。
输入描述:
第一行一个整数nn,表示字符串长度(n<=10^6n<=10
6
)
第二行一个字符串
输出描述:
一个整数,表示最少需要删除的字符数量
示例1
输入
复制
10
NEUUQNEUQQ
输出
复制
2
示例2
输入
复制
9
ILOVENEUQ
输出
复制
5
思路 :
- 总长度减去4*找到的NEUQ个数,这样就不需要特判了
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
char s[N], t[] = "NEUQ";
int main()
{
cin >> n >> s;
int now = 0, cnt = 0;
for (int i = 0; s[i]; i ++ )
{
if (s[i] == t[now])
{
now ++ ;
if (now == 4) now = 0, cnt ++ ;
}
}
cout << n - 4 * cnt;
}