题目：
给定两个怪物
A
A
A和
B
B
B，怪
A
A
A有血量
H
P
A
HP_A
HPA和攻击
A
T
K
A
ATK_A
ATKA，怪
B
B
B有血量
H
P
B
HP_B
HPB和攻击
A
T
K
B
ATK_B
ATKB。有一个人打怪，第
i
i
i秒会发生两件事情：先是仍然存活的怪会对人造成其攻击的伤害，然后人可以选择一只还存活的怪并对这只怪造成
i
i
i点伤害。当怪的血量小于等于0的时候，怪就死了。问满足人受到的伤害最小的情况下的最小字典序的攻击序列。
(
1
≤
H
P
A
,
H
P
B
,
A
T
K
A
,
A
T
K
B
≤
1
0
9
)
(1 \le HP_A,HP_B,ATK_A,ATK_B \le 10^9)
(1≤HPA,HPB,ATKA,ATKB≤109)
题解：
由于每秒钟只能打一只怪，所以怪肯定会先后死亡。设先死的怪为
p
p
p，后死的怪为
q
q
q，那么最小的满足
t
(
t
+
1
)
2
≥
H
P
p
+
H
P
q
\frac{t(t+1)}{2} \ge HP_p+HP_q
2t(t+1)≥HPp+HPq的
t
t
t就是
q
q
q的最早死亡时间，最小的满足
t
1
(
t
1
+
1
)
2
≥
H
P
p
\frac{t_1(t_1+1)}{2} \ge HP_p
2t1(t1+1)≥HPp的
t
1
t_1
t1就是
p
p
p的最早死亡时间，后者是显然的，前者是由于如果
H
P
p
>
∑
i
=
t
1
+
1
t
2
i
HP_p > \sum_{i=t_1+1}^{t_2}i
HPp>∑i=t1+1t2i，那么肯定是因为对怪
p
p
p的伤害溢出了很多，又由于怪
p
p
p受到的是前
t
1
t_1
t1秒的所有伤害，所以肯定可以在前
t
1
t_1
t1秒中取出一个时间
k
=
∑
i
=
1
t
1
i
−
H
P
p
k=\sum_{i=1}^{t_1}i-HP_p
k=∑i=1t1i−HPp，将这个时间的攻击给怪
q
q
q，这样对怪
p
p
p的伤害就是没有溢出的，又由于
t
(
t
+
1
)
2
≥
H
P
p
+
H
P
q
\frac{t(t+1)}{2} \ge HP_p+HP_q
2t(t+1)≥HPp+HPq，所以剩余的伤害足够将怪
q
q
q打死。综上，确定了怪死亡的先后顺序以后，两个怪的死亡时间也可以确定，所以最小伤害也可以确定。
分
A
A
A先死还是
B
B
B先死两种情况，设攻击序列为
Q
Q
Q。
假设
A
A
A先死，贪心地考虑字典序最小，先令
Q
1...
t
1
=
A
Q_{1...t_1}=A
Q1...t1=A，
Q
t
1
+
1...
t
=
B
Q_{t_1+1...t}=B
Qt1+1...t=B，这样有可能会打不死
B
B
B，那么将
k
=
∑
i
=
1
t
1
i
−
H
P
A
k=\sum_{i=1}^{t_1}i-HP_A
k=∑i=1t1i−HPA这一秒的攻击分配给
B
B
B即可。因为这是满足
A
,
B
A,B
A,B均能死亡的最大的
k
k
k，这样可以使字典序最小。
假设
B
B
B先死，那么先令
Q
1...
t
1
=
B
Q_{1...t_1}=B
Q1...t1=B，
Q
t
1
+
1...
t
=
A
Q_{t_1+1...t}=A
Qt1+1...t=A，如果对
B
B
B的伤害有溢出，那么可以从1开始贪心的考虑移除这一秒的伤害，能不能打死怪
B
B
B，如果可以，那么就将这一秒分配给怪
A
A
A，直到不能移除了为止，假设恰好不能移除的这一秒为
k
k
k。这样以后怪
A
A
A还是有可能伤害不够，那么将
k
−
1
k-1
k−1秒对
B
B
B的伤害变成
k
+
∑
i
=
t
1
+
1
t
i
+
∑
i
=
1
k
−
1
i
−
H
P
B
−
1
k+\sum_{i=t_1+1}^{t}i+\sum_{i=1}^{k-1}i-HP_B-1
k+∑i=t1+1ti+∑i=1k−1i−HPB−1这一秒的伤害即可，注意这里不能用移除
A
A
A的溢出伤害的时间来处理，因为怪
B
B
B不够的伤害要小于等于怪
A
A
A溢出的伤害，所以用怪
B
B
B不够的伤害的字典序更小。
复杂度： O ( max { H P A , H P B } ) O(\sqrt{\max \{HP_A,HP_B\}}) O(max{HPA,HPB} )
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<bitset>
#include<sstream>
#include<ctime>
//#include<chrono>
//#include<random>
//#include<unordered_map>
using namespace std;
#define ll long long
#define ls o<<1
#define rs o<<1|1
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
const double pi=acos(-1.0);
const double eps=1e-6;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
ll read(){
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int T,tp;
pii hp,atk;
ll sum[maxn];
char ans1[maxn],ans2[maxn];
int main(void){
// freopen("in.txt","r",stdin);
ll lim=3e9;
tp=0;
while(sum[tp]+tp+1<=lim){
++tp;
sum[tp]=sum[tp-1]+tp;
}
scanf("%d",&T);
while(T--){
scanf("%d%d%d%d",&hp.fi,&hp.se,&atk.fi,&atk.se);
//先A后B
int pos=lower_bound(sum+1,sum+tp+1,hp.fi+hp.se)-sum;
int pos2=lower_bound(sum+1,sum+tp+1,hp.fi)-sum;
ll dam1=1ll*atk.fi*pos2+1ll*atk.se*pos;
for(int i=1;i<=pos2;i++){
ans1[i]='A';
}
for(int i=pos2+1;i<=pos;i++){
ans1[i]='B';
}
if(sum[pos]-sum[pos2]<hp.se){
ll dif=sum[pos2]-hp.fi;
ans1[dif]='B';
}
ans1[pos+1]='\0';
//先B后A
pos2=lower_bound(sum+1,sum+tp+1,hp.se)-sum;
ll rem=sum[pos2],dam2=1ll*atk.se*pos2+1ll*atk.fi*pos;
int tt=pos2+1;
ll cur=0;
for(int i=1;i<=pos2;i++){
if(rem-i>=hp.se){
rem-=i;
ans2[i]='A';
cur+=i;
}
else{
tt=i;
break;
}
}
for(int i=tt;i<=pos2;i++){
ans2[i]='B';
}
for(int i=pos2+1;i<=pos;i++){
ans2[i]='A';
}
cur+=sum[pos]-sum[pos2];
if(cur<hp.fi){
ll dif=hp.fi-cur;
ans2[tt+dif-1]='A';
ans2[tt-1]='B';
}
ans2[pos+1]='\0';
if(dam1<dam2){
printf("%lld %s\n",dam1,ans1+1);
}
else if(dam1>dam2){
printf("%lld %s\n",dam2,ans2+1);
}
else{
if(strcmp(ans1+1,ans2+1)<0){
printf("%lld %s\n",dam1,ans1+1);
}
else{
printf("%lld %s\n",dam1,ans2+1);
}
}
}
return 0;
}