牛客竞赛（字符串+思维）

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

题目描述
给出一个仅包含小写字母的字符串s，你最多可以操作k次，使得任意一个小写字母变为与其相邻的小写字母（ASCII码差值的绝对值为1），请你求出可能的最长相等子序列（即求这个字符串修改至多k次后的的一个最长子序列，且需要保证这个子序列中每个字母相等）。

子序列：从原字符串中取任意多个字母按照先后顺序构成的新的字符串。
示例1
输入

2,“abcde”

返回值

3

示例2
输入

10,“acesxd”

返回值

4

备注:

数据满足：1≤∣s∣≤2^ 10,1≤k≤3000,其中|s|表示字符串的长度。

题意：

对给定的一个字符串进行变换操作，计算在最多限定次数变换的情况下能得到的最长相等子序列的长度
变换：1次只能使1个字母变为和他ASCII码值差的绝对值为1的字母，即b经过一次变换只能变为a或c

思路：

计算使字符串变为a,b,c…z各需要多少次变换，选择出变换次数最小的，使字母串里的字母都变为这个需变换次数最小的字母，然后按照每个字母需变化的次数从小到大排序，最后在计算在限定次数内能变化多少个字母，那么可以变化的字母的个数就是最长相等子序列的长度

代码：

#include
#include
#include
#include
using namespace std;
int main()
{int n;char a[1050];int b[1050];scanf("%d",&n);scanf("%s",a);int l=strlen(a);int i,j,maxx=0;for(i=97; i<=122; i++){for(j=0; j<l; j++){b[j]=abs(i-a[j]);}sort(b,b+j);int s=0,k=0,p;for(p=0; p<l; p++){s=s+b[p];if(s>n)break;elsek++;}maxx=max(maxx,k);}printf("%d\n",maxx);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！