国赛好像考了很多次贪心的思维题，贪心不可小看。
本文给出了蓝桥杯贪心题单链接和部分题目题解。
目录
题单
题干+题解
2018国赛：防御力
题目描述
输入描述
输出描述
输入输出样例
求解
题单
基本蓝桥oj里带“贪心”tag的都能做。
题库 - 蓝桥云课 (lanqiao.cn)
题干+题解
2018国赛：防御力
题目描述
小明最近在玩一款游戏。对游戏中的防御力很感兴趣。
我们认为直接影响防御的参数为"防御性能"，记作 d ，而面板上有两个防御值 A 和 B ，与 d 成对数关系，A=2^d，B=3^d（注意任何时候上式都成立）。
在游戏过程中，可能有一些道具把防御值 A 增加一个值，有另一些道具把防御值 B 增加一个值。
现在小明身上有 n1 个道具增加 A 的值和 n2 个道具增加 B 的值，增加量已知。
现在已知第 i 次使用的道具是增加 A 还是增加 B 的值，但具体使用那个道具是不确定的，请找到一个字典序最小的使用道具的方式，使得最终的防御性能最大。
初始时防御性能为 0，即 d=0，所以A=B=1。
输入描述
输入的第一行包含两个数 n1,n2，空格分隔。
第二行 n1 个数，表示增加 A 值的那些道具的增加量。
第三行 n2 个数，表示增加 B 值的那些道具的增加量。
第四行一个长度为 n1+n2 的字符串，由 0 和 1 组成，表示道具的使用顺序。0 表示使用增加 A 值的道具，1 表示使用增加 B 值的道具。输入数据保证恰好有 n1 个 0，n2 个 1 。
其中，字符串长度 2×10^6，输入的每个增加值不超过 2^30。
输出描述
对于每组数据，输出 n1+n2+1 行。
前 n1+n2 行按顺序输出道具的使用情况，若使用增加A 值的道具，输出 Ax，x 为道具在该类道具中的编号（从 1 开始）。若使用增加 B 值的道具则输出 Bx。
最后一行输出一个大写字母 E 。
输入输出样例
示例
输入
1 2
4
2 8
101
输出
B2
A1
B1
E
求解
简单思维题。
对于d=log2A=log3B，因为A对b增量的贡献比B的大，应先选大的B和小的A，到后面就有大的A能造出最大防御值了。
n1,n2=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
od=list(map(int,input()))
for i in range(n1):
a[i]=[i+1,a[i]]
for i in range(n2):
b[i]=[i+1,b[i]]
a.sort(key=lambda x:x[1],reverse=True)
b.sort(key=lambda x:x[1])
for cur in od:
if cur==0:
t1,t2=a.pop()
print("A"+str(t1))
if cur==1:
t1,t2=b.pop()
print("B"+str(t1))
print("E")
相关文章
您阅读本篇文章共花了：
发表评论