蓝桥杯救命题目系列（一）

admin管理员组

文章数量:1440488

蓝桥杯救命题目系列（一）

1.题目概述

这个题目其实我看了好几天了，这个是苯环哥哥出的一个题目，在洛谷这个网站上，这个网站我一直都有听说过，但是自己也是第一次使用，在这个代码的编译相关的过程上面确实是遇到了很多的问题，现在还没有完全解决，但是我觉得这个时候有点收获，想写一下；

image-20250410202143443

下面的这个就是题目对应的这个相关的输入输出的示例：其实上面的这个文字看的不是很舒服，但是下面的这个输入输出对应的示例看着就比较舒服了，其实这个题目是很容易理解的；

就是希望通过交换让这个AB不是相邻的就可以了，问的就是我们的这个给定的数据需要经过的最小的这个交换的次数罢了：其实一共只有两个可能的情况，其实无非就是ABABAB这个样子的，还有一个就是BABABA这个样子的，只有这两个可能的情况罢了；

我们只需要对于这个给定的数据进行处理，分别处理成为这个ABABABAB类型的，还可以处理成为这个BABABA类型的，看看处理成为哪一个类型对应的这个操作次数是最少的，这个就是我们打印输出的结果，仅此而已；

image-20250410202222720

其实打击可以看到上面的这个数据范围里面是有50%数据怎么怎么样的，这个其实就是我们可以拿到分数的，就是我们通过暴力的求解，去通过这个部分的数据，如果你每一个题目都可以通过部分的数据，这个时候是完全可以拿到省一的，因此这个思路也是我最近正在实行的一个方法；

2.题目思路

下面的这个是苯环哥哥上课的这个板书，使用这个ABABAB作为对应的基准，这个时候如果给出来一个数组就是AAABBB这个样子的，这个时候一一对应处理一下，实际上发现这个里面的第二个和第五个是不一样的，其他的都是一样的，对吧，这个时候，我们只需要对于这个给定的字符串里面的第二个和第五个元素进行位置上面的这个交换就可以了；

如果是下面的那个，这个时候第一个和第四个是一样的，剩下的4个数据是不一致的，这个时候我们只需要进行两次这个交换的过程，一次就是字符串里面的第二三两个位置的元素进行交换，还有一个就是56两个位置的元素进行交换即可；

image-20250410202319343

下面的主要说明一下这个枚举和贪心的体现，这个题目枚举很容易理解，就两个情况，你都去算一下，去两个操作次数里面的最小的数值就可以了，这个就是枚举的思想；

贪心呢？取出来两个数据里面的min值，这个实际上就是一个贪心的策略和我们的人的想法是很相似的，这个就是最简单的这个贪心的思想；

image-20250410202243136

3.代码分析

下面的这个是别人写的代码，首先就是对于这个数据的读取大家是一定需要会的，他这个里面是封装了一个方法，m就是我们的这个过程中会处理几组数据,c数组就是把这个读取的字符串转换为我们的字符数组，方便后面的这个遍历的过程；

而这个问题的精髓，就在于这个solve函数里面呢：countAB,countBA就是对于两个情况下面需要操作的次数分别进行处理，取出来这个min数值就可以了，调用的就是Math里面的取最小值的方法；

for循环就是这个数据统计的关键所在了，他这个事遍历的奇数，c[i]！='A’证明什么，证明这个他是B开头的，拿一个例子来说吧：AAABBB，这个时候第一个元素是A，这个时候就是进入年的else，countba=1，然后就是第三个元素A,还是进入这个else里面去，这个时候countba=2;接下来就是第五个元素countab=1，到此结束;

因此大家就会发现countba=2，这个说明什么，这个转换成为BABABA型的时候操作的次数是2次，这个也侧面验证了我们的这个过程，c[i]!=A的时候（也就是B），转换成为这个BABA型的次数就少一些，因此是加到了转换为ABAB型的这个次数里面去，大家可以这样进行理解；

为什么这个过程是2个两个的进行呢，就是我们上面分析的这个结果，我们4个数据不一致的时候，只需要进行2次的这个变换就可以了，因此这个次数就是不一样的这个元素的个数/2；

代码语言：javascript代码运行次数：0运行复制

import java.util.*;

public class Main {

	public static int solve(char[] c) {
		int countAB = 0,countBA=0;
		for (int i = 0; i < c.length; i += 2) {
			if (c[i] != 'A') {
				countAB++;
			}else {
				countBA++;
			}
		}
		return Math.min(countAB, countBA);
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int m = scanner.nextInt();
		for (int i = 0; i < m; i++) {
			scanner.nextInt();
			char[] c = scanner.next().toCharArray();
			System.out.println(solve(c));
		}
		scanner.close();
	}
}

下面的这个是我自己写的这个代码，思路是一样的，但是只能通过一个测试用例，挺奇怪的，看了很久没发现原因，仅供参考吧，大家可以帮我看一下，上面的那个是没有问题的；

代码语言：javascript代码运行次数：0运行复制

import java.util.*;
public class Main{
        public static void main(String[] args){
            Scanner sc=new Scanner(System.in);
            int t=sc.nextInt();
            for(int i=0;i<t;i++){
                int n=sc.nextInt();
                String str1=sc.nextLine();
                char[] str2=str1.toCharArray();
                int a=0,b=0;
                for(int j=0;j<str2.length;j+=2){
            			if (str2[i] != 'A') {
            				a++;
            			}else {
            				b++;
            			}
                }
                System.out.println(Math.min(a,b));
            }
            sc.close();
        }
}

代码语言：txt复制

System.out.println(Math.min(a,b));
 }
 sc.close();
 }
 }

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-04-10，如有侵权请联系 cloudcommunity@tencent 删除前往查看遍历数据数组字符串网站

本文标签： 蓝桥杯救命题目系列（一）