试题历届真题防御力【第九届】【决赛】【B组】

本文主要是介绍试题历届真题防御力【第九届】【决赛】【B组】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

时间限制：1.0s 内存限制：256.0MB
　　小明最近在玩一款游戏。对游戏中的防御力很感兴趣。
　　我们认为直接影响防御的参数为“防御性能”，记作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。
输出格式
　　对于每组数据，输出n1+n2+1行，前n1+n2行按顺序输出道具的使用情况，若使用增加A值的道具，输出Ax，x为道具在该类道具中的编号（从1开始）。若使用增加B值的道具则输出Bx。最后一行输出一个大写字母E。
样例输入
1 2
4
2 8
101
样例输出
B2
A1
B1
E
样例输入
3 0
7 11 13

000
样例输出
A1
A2
A3
E

样例说明对于第一组测试数据，操作过程如下：操作 d A B初始 0 1 1B2 2 4 9A1 3 8 27B1 log3(29) 2^(log3(29)) 29可以证明，这个值是最大的。对于第二组测试数据，可见无论用什么顺序，A最后总为32，即d总为5，B总为243。

数据规模和约定
　　对于20%的数据，字符串长度<=10000；
　　对于70%的数据，字符串长度<=200000；
　　对于100%的数据，字符串长度<=2000000，输入的每个增加值不超过2^30。

资源约定：
　　峰值内存消耗（含虚拟机） < 256M
　　CPU消耗 < 1000ms

思路：
可以确定是贪心求解，并且A中的尽量挑小的先用，B中尽量挑大的先用（如果相同大小就选字典序小的）
设当前d，A，B
Ai为选的A中的道具值；Bi为选的B中的道具值；
d=log2（A+Ai）
且d=log3(B+Bi)
显然A的变化对d的值影响更大，而B对d的影响值较小，所以根据贪心的思想，既然A的变化对d最终值影响大，那我们就把A中较大的道具留到最后使用，而B对d影响小，所以B中尽量先用大的；
（这道题真的很迷，自己可以例举一下A两个B一个的情况，确实是A应该先用小的，B先用大的，最终d会更大）
code：

import java.util.PriorityQueue;
import java.util.Scanner;class Node3 implements Comparable<Node3>{long val;long loc;public Node3(long vv,long ll){this.loc=ll;this.val=vv;}@Overridepublic int compareTo(Node3 o) {if(this.val!=o.val) {if(o.val>this.val)return 1;else if(o.val<this.val)return -1;else return 0;}else {if(this.loc>o.loc)return 1;else if(this.loc<o.loc)return -1;else return 0;}}	
}class Node4 implements Comparable<Node4>{long val;long loc;public Node4(long vv,long ll){this.loc=ll;this.val=vv;}@Overridepublic int compareTo(Node4 o) {if(this.val!=o.val) {if(o.val>this.val)return -1;else if(o.val<this.val)return 1;else return 0;}else {if(this.loc>o.loc)return 1;else if(this.loc<o.loc)return -1;else return 0;}}	
}public class Main {static int n1,n2;public static void main(String[] args) {Scanner in=new Scanner(System.in);n1=in.nextInt();n2=in.nextInt();PriorityQueue<Node4> q1=new PriorityQueue<>();PriorityQueue<Node3> q2=new PriorityQueue<>();for(long i=1;i<=n1;i++) {long val;val=in.nextInt();q1.add(new Node4(val,i));}for(long i=1;i<=n2;i++) {int val;val=in.nextInt();q2.add(new Node3(val, i));}String op=in.next();if(n1!=0&&n2!=0) {for(int i=0;i<op.length();i++) {if(op.charAt(i)=='0') {Node4 nn=q1.remove();System.out.println("A"+nn.loc);}else {Node3 nn=q2.remove();System.out.println("B"+nn.loc);}}System.out.println("E");}else if(n1==0) {for(int i=0;i<n2;i++) {System.out.println("B"+(i+1));}System.out.println("E");}else if(n2==0) {for(int i=0;i<n1;i++) {System.out.println("A"+(i+1));}System.out.println("E");}}
}