菜鸟集团软开秋招笔试——算法真题

时间：2024.10

1、小红有九个能量石，可以使用一个 A 能量石和一个 B 能量石，造成x点伤害，也可以使用一个 B 能量石和一个 C 能量石，造成y点伤害。小红想知道，最多能造成多少伤害
输入描述：第一行输入一个整数n，表示能量石的数量，第二行输入两个整数x，y，表示造成伤害的两种方式的伤害值，第三行输入一个长度为 n 的字符串 s，表示能量石的种类
输出描述：输出一个整数，表示最多能造成的伤害
示例：输入：
5
12
ABABC
输出：3

2、小红有一个排列，她想让这个排列变成错排，她每次可以交换两个相邻的数，求最小的操作次数。
排列的定义是：一个长度为n 的数组p，1到n 每个数正好出现一次。
错排的定义是：不存在pi=i的排列
输入描述：第一行输入一个整数n，表示数组长度，第二行输入 n 个整数表示排列a
输出描述：输出一个整数表示答案
示例：输入：3
2 1 3
输出：1

3、小红有一些货物准备分拣，她想把这些货物分成两堆，使得其中一堆重量总和是另一堆重量总和的两倍。小红想知道有多少种分拣方案？
由于答案可能过大，请对10^9+7取模
输入描述：第一行输入一个正整数n，代表货物的数量，第二行输入n个正整数ai，代表每个货物的重量
输出描述：一个整数，代表分拣的方案数，答案对10^9+7取模
示例：输入：3
1 2 3
输出：1