蓝桥-防御力

题目

https://www.lanqiao.cn/problems/226/learning/

思路

这其实是一道排序题，要让B从小到大排，A从大到小牌。

但是为什么呢？

让我来数学证明一下~

首先，规定一下符号。

$$\begin{aligned} A_0,B_0表示道具A,B的初始值， a_1,a_2...,b_1,b_2...表示增加A或B的增加量， A_1,A_2...,B_1,B_2...表示增加了某个量之后A，B的值 \end{aligned}$$

和别的地方说的一样，容易说明，连续的增加A或B，顺序是不影响最后的结果的。假设连续增加A，那么$A_n=\log_2{(A_0+a_1+a_2+…)}$，改变顺序不影响$A_n$的值。所以只需要讨论A和B的增加量交替出现的时候如何选择了。

推一下A和B的关系。

$$\begin{aligned} d=\log_2A=\log_3B \\ \frac{\ln A}{\ln2}=\frac{\ln B}{\ln3} \\ \ln A=\ln (B^{\frac{\ln2}{\ln3}}) \\ A=B^{\log_3{2}}\\ 同理可得，B=A^{\log_2{3}} \end{aligned}$$

现在，有$b_1,a_1,b_2$三个增加量，$b_1,b_2$不一样大，先放谁呢？

先算一下先放$b_1$的情况，

$$\begin{aligned} 加上b_1: B_1 &= B_0+b_1 \\ A_1 &= B_1^{\log_3{2}}= (B_0+b_1)^{\log_3{2}}\\ 加上a_1: A_2 &= A_1 + a_1 = (B_0+b_1)^{\log_3{2}} + a_1 \\ B_2 &= A_2^(\log_2{3}) = ( (B_0+b_1)^{\log_3{2}} + a_1 ) ^{\log_2{3}} \\ 加上b_2: B_3 &= B_2 + b_2=((B_0+b_1)^{\log_3{2}}+ a_1 )^{\log_2{3}} + b_2 \\ A_3 &= ... \end{aligned}$$

因为我们最终要d最大，那也就是要A和B最大，所以我们这里就算到$B_3$，如果能让$B_3$尽可能大，那A和d也大了。

同样的可以算一下先放$b_2$的情况，$B_3^{\prime} = ( (B_0+b_2)^{\log_3{2}} + a_1 ) ^{\log_2{3}} + b_1$.

现在假设$B_3^{\prime} \gt B_3^{\prime}$，也就是先放$b_1$使得最后结果更大，求$b_1$和$b_2$谁大了。

$$\begin{aligned} B_3 =((B_0+b_1)^{\log_3{2}} + a_1 ) ^{\log_2{3}} + b_2 \\ B_3^{\prime} = ( (B_0+b_2)^{\log_3{2}} + a_1 ) ^{\log_2{3}} + b_1 \\ B_3 - B_3^{\prime} \gt 0 \\ ( (B_0+b_1)^{\log_3{2}} + a_1 ) ^{\log_2{3}} - ( (B_0+b_2)^{\log_3{2}} + a_1 ) ^{\log_2{3}} \gt b_1 - b_2 \\ \end{aligned}$$

设$f(x)=((B_0+x)^{\log_3{2}} + a_1 ) ^{\log_2{3}}$，因为$\log_2{3}\gt 1$，所以$\frac{f(b_1)-f(b_2)}{b_1-b_2} \gt 1 \$,又有假设$f(b_1)-f(b_2) \gt b_1-b_2$，所以得到 $ b_1 \gt b_2 $。

也就是说，B的增加量是先放大的后放小的。

同理可以说明A是反着的。

代码

# 防御力

n1, n2 = map(int, input().split())
A = list(enumerate(map(int, input().split())))
B = list(enumerate(map(int, input().split())))
A.sort(key=lambda x: x[1])
B.sort(key=lambda x: -x[1])
order = input()
a = b = 0
for c in order:
    if c == "1":  # B
        print(f"B{B[b][0] + 1}")
        b += 1
    elif c == "0":  # A
        print(f"A{A[a][0] + 1}")
        a += 1
print("E")

"""
1 2
4
2 8
101
"""