C语言之小果的键盘
题目背景
小果有一个只有两个键的键盘。
题目描述
一天，她打出了一个只有这两个字符的字符串。当这个字符串里含有VK这个字符串的时候，小果就特别喜欢这个字符串。所以，她想改变至多一个字符（或者不做任何改变）来最大化这个字符串内VK出现的次数。给出原来的字符串，请计算她最多能使这个字符串内出现多少次VK（只有当V和K正好相邻时，我们认为出现了VK。）
输入格式
第一行给出一个数字 n，代表字符串的长度。
第二行给出一个字符串 s。
输出格式
第一行输出一个整数代表所求答案。
思考历程
又没有好好看题目意思，题目要求的是最多改变一个字符，要求出现最多的vk，一开始没有考虑直接写，分可低了。下面的代码没有考虑左右字符的影响，没有考虑边界情况，所以肯定不对
#include<stdio.h> int main() { int n; while(scanf("%d",&n)!=EOF){ while(getchar()!='\n'); char s[n+1]; fgets(s,sizeof(s),stdin); int i; int count=0; for(i=0;i<n-1;i++){ if(s[i]=='V'&&s[i+1]=='K'||s[i]=='K'&&s[i+1]=='V'){ count++; } } printf("%d",count); } return 0; }正确答案：
#include<stdio.h> #include<string.h> int main() { int n; char s[101];//千万注意不要写成int类型 while(scanf("%d",&n)==1&&n!=0){ scanf("%s",s);//把字符串赋值给字符串数组 int i; int original_count=0;//没改字符之前统计的vk数量 for(i=0;i<n-1;i++){ if(s[i]=='V'&&s[i+1]=='K'){ original_count++; } } int max_delta=0; for(i=0;i<n;i++){ char old_char=s[i];//把所有的字符赋值给old_char，用于记录当前位置原来的字符 char new_char=(old_char=='V')?'K':'V';//改变字符，如果是v就改成k，如果是k就改成v。 int delta=0;//计算变化量 if(i-1>=0){//因为i=0时没有s[i-1] int old1_is_vk=(s[i-1]=='V'&&old_char=='K'); int new1_is_vk=(s[i-1]=='V'&&new_char=='K'); delta+=(new1_is_vk?1:0)-(old1_is_vk?1:0);//计算vk组合新增加的数量。 } if(i+1<n){//因为有i+1，不能超过n，一开始的i=0肯定不满足上述条件 int old2_is_vk=(old_char=='V'&&s[i+1]=='K'); int new2_is_vk=(new_char=='V'&&s[i+1]=='K'); delta+=(new2_is_vk?1:0)-(old2_is_vk?1:0); } if(delta>max_delta){//因为最后要找出改变字符后的最大组合量，所以要和原来有比较 max_delta=delta; } } int result=original_count+(max_delta>0?max_delta:0);max_delta表示的是改变字符后新增加的组合量 printf("%d\n",result); } return 0; }一.上述代码是模拟修改，不是真的修改，所以不满足条件的不用再修改回来
因为修改一个字符影响的是和前一个字符配对，和后一个字符配对，所以只需要考虑这两部分即可。（i-1,i)和(i,i+1)这两部分。当考虑到这两部分之后，就要考虑i-1必须要大于0，i+1必须要小于0.
for(i=0;i<n;i++){
char old_char=s[i];
char new_char=(old_char=='V')?'K':'V';
int delta=0;
if(i-1>=0){
int old1_is_vk=(s[i-1]=='V'&&old_char=='K');
int new1_is_vk=(s[i-1]=='V'&&new_char=='K');
delta+=(new1_is_vk?1:0)-(old1_is_vk?1:0);
}
if(i+1<n){
int old2_is_vk=(old_char=='V'&&s[i+1]=='K');
int new2_is_vk=(new_char=='V'&&s[i+1]=='K');
delta+=(new2_is_vk?1:0)-(old2_is_vk?1:0);
}
用示例来解析上述代码：
假设字符串是VVK
第一次循环i=0，考虑修改第一个字符
old_char = s[0] = 'V' new_char = 'K' // V改为K // 计算改变影响： // 只有(i,i+1)即(0,1)受影响 // 改变前：'V'(old)和'V'(s[1]) → "VV" 不是VK // 改变后：'K'(new)和'V'(s[1]) → "KV" 不是VK // delta = 0-0 = 0 //上述部分只符合下面的if语句，所以只有一部分delta第二次循环i=1,考虑修改第二个字符
old_char = s[1] = 'V' new_char = 'K' // V改为K // 计算改变影响： // (i-1,i)即(0,1)：改变前"VV"(0)，改变后"VK"(+1) → delta_part1 = 1 // (i,i+1)即(1,2)：改变前"VK"(1)，改变后"KK"(0) → delta_part2 = -1 // total_delta = 1 + (-1) = 0 //当改变第二个字符的时候，既符合上述if语句，又符合下面的if语句，所以有两部分delta，原来是VV，不符合上述判断vk，所以old1_is_vk=0,而修改第二个字符之后变成VK，符合杉树判断，所以第一部分delta是1，同时下面的if同样计算，最后得出总的delta第三次循环i=2，考虑修改第三个字符
old_char = s[2] = 'K' new_char = 'V' // K改为V // 计算改变影响： // 只有(i-1,i)即(1,2)受影响 // 改变前：'V'(s[1])和'K'(old) → "VK" 是VK // 改变后：'V'(s[1])和'V'(new) → "VV" 不是VK // delta = 0-1 = -1 //i=2时只符合上述if语句，所以只计算一次就🆗