The 2018 ACM-ICPC Asia Jiaozuo Regional Contest B.Ultraman vs. Aodzilla and Bodzilla
题目链接
http://codeforces.com/gym/102028/problem/B
题目大意
你的奥特曼需要消灭两个 血量、攻击力 分别为 $HPA, HPB, ATKA, ATKB$ 的 $A, B$ 两个怪兽，第 $i$ 秒奥特曼可以选择对任意一个还活着的怪兽造成 $i$ 点伤害，每秒存活的怪兽都会攻击奥特曼并造成相应的伤害。问奥特曼消灭两个怪兽所受的最小伤害和对应的最小字典序的攻击方案。
题目分析
令 $f(i) = \frac{i(i + 1)}{2}$
显然可知，只有当奥特曼在最小的 $x$ 使得 $f(x) \leq HPA + HPB$ 时，收到的伤害最小。之后考虑 $A$ 和 $B$ 谁先死亡，则有最小的时刻应该分别为是最小的 $f(y_A) \leq HPA$ 和 $f(y_B) \leq HPB$ 时有最小值。
对于每次出现的最小值，再考虑构造最小的字典序。
在 $A$ 先死的情况下，比较好处理，如果 $f(y_A) – HPA > 0$ 且 有 $f(x) – f(y_A) < HPB$ ，则需要在 $f(y_A) – HPA$ 时刻攻击一下 $B$ ，以达到在 $f(x)$ 时间内可以消灭 $B$，否则直接前 $y_A$ 次攻击 $A$ 即可。
在 $B$ 先死的情况下，则需要考虑如何将 $f(y_B) – HPB$ 这多余的攻击点数利用到 $A$ 上。考虑到要求字典序最小，那么越早攻击 $A$ 越好，但需要注意到，只有当 $f(x) – f(y_B)$ 比攻击剩余的 $HPA$ 要大的时候才可以随便攻击，否则一定要保证攻击完之后剩余的可利用的部分可以某一时刻 $i$ 秒被消耗掉。以此构建字典序最小攻击策略。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 5;
int t;
long long hpa, hpb, atka, atkb;
long long ans[5][2];
string str[5];
long long read(){
long long x;
scanf("%lld", &x);
return x;
}
int geta(long long hp){
long long i = sqrt(hp * 2);
while(i * (i + 1) / 2 < hp){
i++;
}
while(i * (i - 1) / 2 >= hp){
i--;
}
return i;
}
long long f(long long x){
return x * (x + 1) / 2;
}
int main(){
int i, j;
long long l, r;
int mid;
long long minx;
string anss;
t = read();
while(t--){
hpa = read();
hpb = read();
atka = read();
atkb = read();
minx = 1e18 + 7;
str[0] = str[1] = "";
ans[0][0] = geta(hpa);
ans[0][1] = geta(hpa + hpb);
for(i=1;i<=ans[0][0];i++){
if(i == f(ans[0][0]) - hpa and f(ans[0][1]) - f(ans[0][0]) < hpb){
str[0].push_back('B');
}else{
str[0].push_back('A');
}
}
for(i=ans[0][0]+1;i<=ans[0][1];i++){
str[0].push_back('B');
}
ans[1][0] = geta(hpb);
ans[1][1] = geta(hpa + hpb);
l = f(ans[1][0]) - hpb;
r = 0;
for(i=1;i<=ans[1][0];i++){
if(l == i or (l > i and (l - i > i or hpa - r - i <= f(ans[1][1]) - f(ans[1][0])))){
l -= i;
r += i;
str[1].push_back('A');
}else{
str[1].push_back('B');
}
}
for(i=ans[1][0]+1;i<=ans[1][1];i++){
str[1].push_back('A');
}
if(ans[0][0] * atka + ans[0][1] * atkb < ans[1][0] * atkb + ans[1][1] * atka){
minx = ans[0][0] * atka + ans[0][1] * atkb;
anss = str[0];
}else if(ans[0][0] * atka + ans[0][1] * atkb > ans[1][0] * atkb + ans[1][1] * atka){
minx = ans[1][0] * atkb + ans[1][1] * atka;
anss = str[1];
}else{
minx = ans[1][0] * atkb + ans[1][1] * atka;
anss = min(str[0], str[1]);
}
printf("%lld %s\n", minx, anss.c_str());
}
return 0;
}