NEUQ 字符串 第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛

链接: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;
}

上一篇:dubbo之服务本地暴露


下一篇:湖南大学2021届ACM新生赛【题目全解】——补题ing