k8s 5G windows postgresql input odbc vue路由 vue的优点 java并发编程视频 excel动态图表制作 matlab对数函数 js获取body的高度 winbox使用教程 nodejs后端开发 js控制台打印 python中文手册 python位运算 python的文件操作 python匹配字符串 python获取输入 java替换字符串 java得到当前时间 java创建目录 java的安装 java中的泛型 金山wps2003 信息系统项目管理师教程 ram容量是什么意思 橄榄山快模 给视频加字幕的软件 掌门一对一下载 小洛快跑 pycharm中文版 文明6万神殿 cad特性匹配 0x000007a cinema4d下载 加速软件 jquery下载 stata
当前位置: 首页 > 学习教程  > 编程语言

最长相等子序列

2020/12/5 9:44:44 文章标签:

链接:https://ac.nowcoder.com/acm/contest/9715/B 来源:牛客网 时间限制:C/C 1秒,其他语言2秒 空间限制:C/C 131072K,其他语言262144K 64bit IO Format: %lld 题目描述 给出一个仅包含小写字母的字符串s&…

链接:https://ac.nowcoder.com/acm/contest/9715/B
来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format: %lld
题目描述
给出一个仅包含小写字母的字符串s,你最多可以操作k次,使得任意一个小写字母变为与其相邻的小写字母(ASCII码差值的绝对值为1),请你求出可能的最长相等子序列(即求这个字符串修改至多k次后的的一个最长子序列,且需要保证这个子序列中每个字母相等)。

子序列:从原字符串中取任意多个字母按照先后顺序构成的新的字符串。
示例1
输入
2,“abcde”
返回值
3
示例2
输入
10,“acesxd”
返回值
4
备注:
来源:牛客网
1<=|s|<=2^10 ,1≤k≤3000,其中|s|表示字符串的长度。
题解:每个字母一次变化只能变成比这个字母大1或者小1的字母,a<=每个字母<=z,用a—z去遍历一遍,若都换成a时,每个字母需要的步数存在一个数组中,对这个数组进行排序,判断不超过k步时,最多能交换几个字母,同理,都换成b时…,换成z时…取这个数量的最大值
代码如下:

#include<stdio.h>
#include<string.h>
char s[5000],k;
int string2(int k, char* s )
{
    int i,l,t,v,a[2060],maxx=-1,x=0;
    char j,c;
    l=strlen(s);
    for(j='a'; j<='z'; j++)
    {
        int ans=0,h=0;
        for(i=0; i<l; i++)
        {
            t=s[i]-j;
            if(t<0)
                t=-t;
            a[h++]=t;
        }
        for(i=0; i<h-1; i++)
        {
            for(v=0; v<h-1-i; v++)
            {
                if(a[v]>a[v+1])
                {
                    t=a[v];
                    a[v]=a[v+1];
                    a[v+1]=t;
                }
            }
        }
        t=0;
        for(i=0;i<h;i++)
        {
            ans+=a[i];
            t++;
            if(ans>k)
            {
                t--;
                break;
            }
        }
        if(maxx<t)
            maxx=t;
    }
    return maxx;
}
int main()
{
    scanf("%d %s",&k,s);
    printf("%d\n",string2(k,s));
    return 0;
}


本文链接: http://www.dtmao.cc/news_show_450069.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?