当前位置:网站首页>第九届 蓝桥杯 决赛 交换次数
第九届 蓝桥杯 决赛 交换次数
2022-07-07 15:32:00 【@小红花】
问题描述
IT产业人才需求节节攀升。业内巨头百度、阿里巴巴、腾讯(简称BAT)在某海滩进行招聘活动。
招聘部门一字排开。由于是自由抢占席位,三大公司的席位随机交错在一起,形如:
ABABTATT,这使得应聘者十分别扭。
于是,管理部门要求招聘方进行必要的交换位置,使得每个集团的席位都挨在一起。即最后形如:
BBAAATTT 这样的形状,当然,也可能是:
AAABBTTT 等。现在,假设每次只能交换2个席位,并且知道现在的席位分布,
你的任务是计算:要使每个集团的招聘席位都挨在一起需要至少进行多少次交换动作。输入是一行n个字符(只含有字母B、A或T),表示现在的席位分布。
输出是一个整数,表示至少交换次数。比如,输入:
TABTABBTTTT程序应该输出:
3再比如,输入:
TTAAABB程序应该输出:
0我们约定,输入字符串的长度n 不大于10万
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是:Main,否则按无效代码处理。
Java
import java.util.Scanner;
public class 交换次数 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
char[] ss = scanner.next().toCharArray();
//六种排列组合的方案
char[][] c = {
{'B','A','T'},
{'B','T','A'},
{'A','B','T'},
{'A','T','B'},
{'T','A','B'},
{'T','B','A'}
};
int ans = Integer.MAX_VALUE;
for(int i = 0;i < 6;i++) {
ans = Math.min(ans,fun(ss,c[i][0],c[i][2],c[i][2]));
}
System.out.println(ans);
}
//将整个字符串分为三个区域
public static int fun(char[] ss,char A,char B,char C) {
//A区域中a的个数
int a = 0;
//B区域中b的个数
int b = 0;
//A区域中非a的个数
int Abc = 0;
//A区域中b的个数
int Ab = 0;
//B区域中a的个数
int Ba = 0;
//B区域中c的个数
int Bc = 0;
int len = ss.length;
//求出A和B两个区域占的大小
for(int i = 0;i < len;i++) {
if(ss[i] == A) a++;
if(ss[i] == B) b++;
}
for(int i = 0;i < a;i++) {
if(ss[i] != A) Abc++;
if(ss[i] == B) Ab++;
}
for(int i = a;i < a + b;i++) {
if(ss[i] == A) Ba++;
if(ss[i] == C) Bc++;
}
//最小交换次数是:将A区域非a的交换出去,B区域非b的交换出去
//因为A区域中有b,B区域中有a,他们直接交换就行,再减去重复的交换次数
return Abc + Bc + Ba - Math.min(Ba, Ab);
}
}
边栏推荐
- logback. XML configure logs of different levels and set color output
- 记录Servlet学习时的一次乱码
- Laravel 服务提供者实例教程 —— 创建 Service Provider 测试实例
- Binary search tree (basic operation)
- 偶然升职的内心独白
- 运算符
- Cesium(3):ThirdParty/zip. js
- 【Android -- 数据存储】使用 SQLite 存储数据
- Horizontal and vertical centering method and compatibility
- 低代码(lowcode)帮助运输公司增强供应链管理的4种方式
猜你喜欢
最新高频Android面试题目分享,带你一起探究Android事件分发机制
【MySql进阶】索引详解(一):索引数据页结构
使用JSON.stringify()去实现深拷贝,要小心哦,可能有巨坑
两类更新丢失及解决办法
爬虫(17) - 面试(2) | 爬虫面试题库
AutoLISP series (3): function function 3
[Android -- data storage] use SQLite to store data
Personal notes of graphics (4)
Record the migration process of a project
The latest interview experience of Android manufacturers in 2022, Android view+handler+binder
随机推荐
What is the difference between IP address and physical address
最新高频Android面试题目分享,带你一起探究Android事件分发机制
Personal notes of graphics (3)
Deep listening array deep listening watch
面试题 01.02. 判定是否互为字符重排-辅助数组算法
Introduction to ThinkPHP URL routing
01tire+链式前向星+dfs+贪心练习题.1
Interface oriented programming
Spark Tuning (III): persistence reduces secondary queries
Ray and OBB intersection detection
LeetCode-SQL第一天
在哪个期货公司开期货户最安全?
Introduction and use of gateway
time标准库
[vulnhub range] thales:1
使用JSON.stringify()去实现深拷贝,要小心哦,可能有巨坑
Tragedy caused by deleting the console statement
PHP实现微信小程序人脸识别刷脸登录功能
[summary of knowledge] summary of notes on using SVN in PHP
模拟Servlet的本质