题解 | #打怪#

打怪

当游戏结束时必须满足以下两个条件之一：

• 攻击力等于对方的血量
• 防御力等于对方的攻击力

当攻击力为a时，防御力为b时。获得一个金币的代价为$\lfloor \frac{HP-1}{a}\rfloor \ast (AD-b)\backslash lfloor\backslash frac\{HP-1\}\{a\}\backslash rfloor*(AD-b)$

对于任何一种情况来说都可以归纳成以下表格情况情况: ($w_i=\lfloor \frac{HP-1}{i}\rfloor ,i\mathrm{可}\mathrm{以}\mathrm{比}HP\mathrm{大}w\_i=\backslash lfloor\backslash frac\{HP-1\}\{i\}\backslash rfloor,\; i可以比HP大$)

我们可以观察到升级防御时后，将会出现两次$w_{i}w\_i$。 之后将相同攻击次数的情况划分成同一类后获得$\sqrt{n}\backslash sqrt\{n\}$不同的数，对于某个攻击次数为$yy$、个数为$lenlen$的情况，贪心考虑后得到两种代价，每次选择代价小的那个，然后累计到ans上。

• 为扣血量x的最后一个：$(x\ast y)+((x-1)\ast y\ast len)(x\; *\; y)+((x-1)*y*len)$
• 不是最后一个：$x\ast len\ast yx*len*y$

当攻击力等于对方的血量时，$y=0y=0$ 防御力等于对方的攻击力，$x=0x=0$

对于中间的任何情况来说，结束的代价为$ans+(1+x)\ast x\mathrm{/}2\ast yans+(1+x)*x/2*y$。 当$x=0x=0$时退出循环即可：

void slove() {
    ll ad = read(), hp = read();
    hp--;
    ll res = hp * (1 + ad) * ad / 2, ans = 0;
    ll x = ad;
    for (ll l = 1, r, y; l <= hp && x > 0; l = r + 1) {
        y = hp / l, r = hp / y;
        ll len = r - l + 1;
        // 总代价
        res = min(res, y * x * (1 + x) / 2 + ans);

        if (x - len <= 0) {
            ans += (2 * x - 1) * len * y;
            x--;
        } else ans += x * len * y;
    }
    print(min(res, ans));
}