B. Ultraman vs. Aodzilla and Bodzilla
题目大意:
两只怪兽A和B,血量分别为hpa,hpb,攻击力分别为atka,atkb。
英雄每一轮只能对一只怪兽进行攻击,第i次攻击伤害为i。
怪兽每一轮比英雄先攻击,伤害为存活怪兽伤害总和。
求出英雄最小受到的伤害,并且输出英雄攻击字典序。
解题思路:
- 非常显而易见的一个思路就是肯定要先把其中一只怪兽打死,然后集中攻击剩下的怪兽
-
那么我们一只打A再打B,或者一直打B再打A不就行了(这样子铁错了)
1
5 5 5 5
正确:35 ABBA
错误:40 AAABB
- 观察可以发现就算要先把一只怪兽打死,但我们可能中间需要穿插一些对另一只怪兽的攻击
- 先将1~i轮攻击伤害总和用pri数组存起来
先打A:
-
令u1=lower_bound(pri + 1, pri + maxn, hpa) - pri
,u2=lower_bound(pri + 1, pri + maxn, hpa + hpb) - pri
- u1 代表一直打A需要的攻击次数,u2代表攻击两只怪兽血量总和需要的次数
- 分两种情况讨论:
当pri[u2]-pri[u1]>=hpb:
说明 u1+1 ~ u2 轮持续不断攻击B能恰好攻击掉B,此时答案即为最优情况。
当pri[u2]-pri[u1]<hpb:
说明 u1+1 ~ u2 轮持续不断攻击B并不能使B死亡
且又说明pri[u1]打A会有溢出攻击p,如果此时的溢出攻击刚好给B就能使B死亡
所以只要在第p轮攻击B即可,因为要字典序最小,所以这个最靠后的位置最好
先打B:
-
令u1=lower_bound(pri + 1, pri + maxn, hpb) - pri
,u2=lower_bound(pri + 1, pri + maxn, hpa + hpb) - pri
- u1 代表一直打B需要的攻击次数,u2代表攻击两只怪兽血量总和需要的次数
- 分两种情况讨论:
前面可以最前面插入连续一段的A去抵消B的多余伤害,
且此时这段连续的A的攻击伤害 + 后面连续攻击A的伤害 >= hpa
设left为u2轮之后,A剩余的血量(不为0)
在前面此时for循环判断有哪些可以改为攻击A
条件为 left - i > i || left == i
这样既能保证恰好攻击完left,又能保证不会影响B
因为u2轮能把hpa+hpb攻击完,而hpa在 u1+1 ~ u2 攻击不完,说明hpb在u1轮攻击完之后必然会有攻击溢出
此时这里的操作就相当于把攻击溢出分出来一部分攻击A
AC代码:
// #include <bits/stdc++.h>
#include <iostream>
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair <string, ll> psl;
const int maxn = 1e5 + 10;
ll hpa, hpb, atka, atkb;
ll pri[maxn];
psl ans1, ans2;
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for (int i = 1; i < maxn; i++)
pri[i] = pri[i - 1] + i;
int _;
cin >> _;
while (_--) {
ans1 = {"", 0}, ans2 = {"", 0};
cin >> hpa >> hpb >> atka >> atkb;
//先攻击A
int u1 = lower_bound(pri + 1, pri + maxn, hpa) - pri;
int u2 = lower_bound(pri + 1, pri + maxn, hpa + hpb) - pri;
ans1.second = u1 * atka + u2 * atkb;
ll left;
if (pri[u2] - pri[u1] >= hpb) {
for (int i = 1; i <= u1; i++)
ans1.first += 'A';
for (int i = u1 + 1; i <= u2; i++)
ans1.first += 'B';
}
else {
left = pri[u1] - hpa;
for (int i = 1; i <= u1; i++) {
if (i == left) ans1.first += 'B';
else ans1.first += 'A';
}
for (int i = u1 + 1; i <= u2; i++)
ans1.first += 'B';
}
//先攻击B
u1 = lower_bound(pri + 1, pri + maxn, hpb) - pri;
u2 = lower_bound(pri + 1, pri + maxn, hpa + hpb) - pri;
ans2.second = u1 * atkb + u2 * atka;
int pos = upper_bound(pri + 1, pri + maxn, pri[u1] - hpb) - pri - 1;
if (pri[pos] + pri[u2] - pri[u1] >= hpa) {
for (int i = 1; i <= u1; i++)
if (i <= pos) ans2.first += 'A'; //前面连续一段都改为A
else ans2.first += 'B';
for (int i = u1 + 1; i <= u2; i++)
ans2.first += 'A';
}
else {
// cout << "?";
left = hpa - (pri[u2] - pri[u1]);
for (int i = 1; i <= u1; i++) {
if (left - i > i || left == i)
left -= i, ans2.first += 'A'; //替换
else
ans2.first += 'B';
}
for (int i = u1 + 1; i <= u2; i++)
ans2.first += 'A';
}
if (ans1.second < ans2.second) cout << ans1.second << " " << ans1.first << endl;
else if (ans1.second > ans2.second) cout << ans2.second << " " << ans2.first << endl;
else {
if (ans1.first > ans2.first) cout << ans2.second << " " << ans2.first << endl;
else cout << ans1.second << " " << ans1.first << endl;
}
}
}