编程论坛 → C++教室

一道算法题

codeooo 发布于 2019-03-15 16:19， 2747 次点击

跪求大佬解决。。。。
题目是这样的：给定一字符串S，S非空，由小写字母组成，设v为S中元音字母的个数，c为辅音字母的个数。"a", "e", "i", "o", "u"为元音字母。其余为辅音字母。如果元音字母没有超过辅音字母的2倍，即v≤2c则称S是好的字符串。

现在给定S，找出其中最长的好的子串的长度，以及个数。子串是由原串中连续的几个字符组成的。

下面是我写的代码。。。。大多都AC了可还是有几个显示超时了。。附件里面有一个我通过不了的输入。。它的输出是66 23988

只有本站会员才能查看附件，请登录

程序代码：

#include <cmath>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

int main() {
    string a;
    cin >> a;
    int lnum = 0;
    int n = 0;
    int inum,bnum;
    for(int i = 0; i < a.size();i++)
    {
        inum = bnum =0;
        for(int j = i; j < a.size();j++){
            switch(a[j]){
                case 'a':
                case 'e':
                case 'i':
                case 'o':
                case 'u':
                inum++;
                break;
                default:
                bnum++;
                break;
            }
            if(inum <= 2 * bnum){
                if(j+1-i > n){
                    n  = j+1-i;
                    lnum = 0;
                }
                if(j+1-i == n){
                lnum++;
            }
            }
        }
    }
    if(lnum == 0){
        cout << "No solution" <<endl;
    }
    else{
        cout << n <<" "<< lnum <<endl;
    }

    return 0;
}

10 回复

#2

rjsp2019-03-15 16:49

首先，要贴链接（https://www.）
如果你觉得链接是不可告人的机密的话，那么最起码题目要求要贴完整。

你的代码正确与否先不谈，有算法吗？如果只是写几个for过关，那是自己骗自己呀。（今天周末，我没时间解答了）

#3

rjsp2019-03-15 16:54

没时间解答，就说说解题思路吧
类似于求最长的和为正数的子序列，只需要遍历一次。遇到元音字母-1，遇到辅音字母+2

#4

codeooo2019-03-16 10:39

回复 2楼 rjsp

呃。。。当初想的是还要跳转链接会麻烦别人就没有弄了。。。

#5

codeooo2019-03-16 10:41

回复 3楼 rjsp

是还要加一个独立的数组来解决计数问题吗?

#6

zolin2019-03-17 12:13

#include <iostream>
int yuan(char * in);
int fu(char * in);

int main()
{
    using namespace std;
    char s[50];
    int f = 0;
    int y = 0;
    cout << "请输入一串字符：";
    cin.get(s, 50);
    f = fu(s);
    y = yuan(s);
    if (f * 2 > y)
    {
        cout << s << "\n" << "元音字母：" << y << "副音字母：" << f;

    }
    else
    {
        cout << "你的字符串是错误的!!!";
    }
    return 0;
}
int yuan(char * in)
{
    int i = 0;
    int count = 0;
    while (in[i]!='\0' )
    {
        switch (in[i])
        {
            case 'a':
            count++;break;
            case 'e':
                count++;
            break;
            case 'i':
                count++;
            break;
            case 'o':
                count++;
            break;
            case 'u':
                count++;
            break;
        }
        i++;

    }
    return count;
}
int fu(char * in)
{
    int i = 0;
    int count = 0;
    while (in[i]!= '\0')
    {
        switch (in[i])
        {
        case 'a':
            break;
        case 'e':
            break;
        case 'i':
            break;
        case 'o':
            break;
        case 'u':
            break;
        default: count++;

        }
        i++;
    }
    return count;
}

#7

rjsp2019-03-18 09:52

https://blog.

#8

rjsp2019-03-18 14:42

附件里面有一个我通过不了的输入。。它的输出是66 23988

你是指你的程序输出66 23988，还是指正确的输出应该是66 23988 ？
可能，你的程序输出66 480，正确的输出也应该是66 480。

我写了一个对照程序

程序代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int main( void )
{
    static int buf[200000]; // buf[i]记录着 (字符串前i个字符中的元音字符的个数)*3-2*i
    int n = 0;
    {
        int vowel_sum = 0;
        for( int ch; ch=getchar(), ch>='a' && ch<='z'; ++n )
        {
            switch( ch )
            {
            case 'a': case 'e': case 'i': case 'o': case 'u':
                ++vowel_sum;
            }
            buf[n] = 3*vowel_sum - 2*n;
        }
    }

    static int rmin[200000]; // buf[i]记录着 buf[i]至buf[n-1]所有元素中的最小值
    {
        int tmp = INT_MAX;
        for( int i=0; i!=n; ++i )
        {
            tmp = std::min(tmp,buf[n-1-i]);
            rmin[n-1-i] = tmp;
        }
    }

    size_t max_len = 0;
    size_t max_len_count = 0;
    for( int i=0; i!=n; ++i )
    {
        size_t len = upper_bound( rmin+i, rmin+n, i==0?2:buf[i-1] ) - (rmin+i);
        if( len > max_len )
        {
            max_len = len;
            max_len_count = 1;
        }
        else if( len == max_len )
        {
            ++max_len_count;
        }
    }

    if( max_len == 0 )
        puts( "No solution" );
    else
        printf( "%zu %zu\n", max_len, max_len_count );

    return 0;
}

#9

codeooo2019-03-19 10:40

回复 8楼 rjsp

正确的输出是23988，然鹅我算的是480.。。。。。。
很抱歉昨天忘记看帖子没有及时回复

#10

codeooo2019-03-19 10:49

回复 6楼 zolin

兄弟，你这个固定数组长度。。。不太行吧。。。。。。。但还是非常感谢

[此贴子已经被作者于2019-3-19 10:51编辑过]

#11

rjsp2019-03-19 12:06

回复 9楼 codeooo

正确的就应该是480吧，我的代码算出来也是480
而且，我的代码已经提交通过了。

1