当前位置：首页 > news >正文

[蓝桥杯]防御力

news 2025/7/4 7:52:38

防御力

题目描述

小明最近在玩一款游戏。对游戏中的防御力很感兴趣。

我们认为直接影响防御的参数为"防御性能"，记作 dd ，而面板上有两个防御值 AA 和 BB ，与 dd 成对数关系，A=2d，B=3dA=2d，B=3d（注意任何时候上式都成立）。

在游戏过程中，可能有一些道具把防御值 AA 增加一个值，有另一些道具把防御值 BB 增加一个值。

现在小明身上有 n1n1 个道具增加 AA 的值和 n2n2 个道具增加 BB 的值，增加量已知。

现在已知第 ii 次使用的道具是增加 AA 还是增加 BB 的值，但具体使用那个道具是不确定的，请找到一个字典序最小的使用道具的方式，使得最终的防御性能最大。

初始时防御性能为 00，即 d=0d=0，所以 A=B=1A=B=1。

输入描述

输入的第一行包含两个数 n1,n2，空格分隔。

第二行 n1 个数，表示增加 A 值的那些道具的增加量。

第三行 n2 个数，表示增加 B 值的那些道具的增加量。

第四行一个长度为 n1+n2 的字符串，由 0 和 1 组成，表示道具的使用顺序。0 表示使用增加 A 值的道具，1 表示使用增加 B 值的道具。输入数据保证恰好有 n1 个 0，n2 个 1 。

其中，字符串长度 ≤2×106≤2×106，输入的每个增加值不超过 230230。

输出描述

对于每组数据，输出 n1+n2+1n1+n2+1 行。

前 n1+n2n1+n2 行按顺序输出道具的使用情况，若使用增加AA 值的道具，输出 Ax，xAx，x 为道具在该类道具中的编号（从 1 开始）。若使用增加 BB 值的道具则输出 BxBx。

最后一行输出一个大写字母 E 。

输入输出样例

示例

输入

输出

B2
A1
B1
E

运行限制

最大运行时间：1s
最大运行内存: 256M

总通过次数: 1576 | 总提交次数: 1747 | 通过率: 90.2%

难度: 困难标签: 2018, 贪心, 国赛

算法思路及原理

核心贪心策略

A类道具：按增加量从小到大排序，相同增加量时按原始编号从小到大排序
B类道具：按增加量从大到小排序，相同增加量时按原始编号从小到大排序
操作序列：按照输入字符串的顺序，遇到'0'选择下一个A道具，遇到'1'选择下一个B道具

数学原理

防御性能 d 由 A = 2^d 和 B = 3^d 决定
使用B道具时，优先使用大增加量可快速提升B值，从而在后续操作中获得更高的d值增长
使用A道具时，优先使用小增加量避免过早提升A值导致后续B道具效果减弱
相同增加量时按编号排序保证字典序最小

算法过程演示

以样例输入1 2\n4\n2 8\n101为例：

C++代码实现：防御性能最大化策略

我将为你提供完整的C++解决方案，包含算法思路、代码解析、实例验证和优化建议。该算法基于贪心策略，确保防御性能最大化的同时满足字典序最小要求。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;struct Item {long long val;  // 道具增加量int id;         // 道具原始编号
};// A道具比较函数：按值升序，值相同按编号升序
bool cmpA(const Item& a, const Item& b) {if (a.val != b.val) return a.val < b.val;return a.id < b.id;
}// B道具比较函数：按值降序，值相同按编号升序
bool cmpB(const Item& a, const Item& b) {if (a.val != b.val) return a.val > b.val;return a.id < b.id;
}int main() {// 提高I/O效率ios::sync_with_stdio(false);cin.tie(nullptr);int n1, n2;scanf("%d %d", &n1, &n2);// 读取A道具并记录原始编号vector<Item> A(n1);for (int i = 0; i < n1; i++) {scanf("%lld", &A[i].val);A[i].id = i + 1;}// 读取B道具并记录原始编号vector<Item> B(n2);for (int i = 0; i < n2; i++) {scanf("%lld", &B[i].val);B[i].id = i + 1;}// 读取操作序列字符串char s[2000010];  // 最大长度2e6scanf("%s", s);string ops(s);// 对道具进行排序sort(A.begin(), A.end(), cmpA);sort(B.begin(), B.end(), cmpB);int idxA = 0, idxB = 0;  // 道具索引指针vector<string> result;    // 存储结果序列// 按操作序列选择道具for (char op : ops) {if (op == '0') {result.push_back("A" + to_string(A[idxA].id));idxA++;} else if (op == '1') {result.push_back("B" + to_string(B[idxB].id));idxB++;}}// 输出结果for (const string& line : result) {printf("%s\n", line.c_str());}printf("E\n");return 0;
}