AT2580 题解

前言

题目传送门！

更好的阅读体验？

这题是常规的二分答案。

前置知识：二分答案

教大家一个小技巧：如何判断一题是否可以使用二分答案，以及如何编写程序？

1. 设计 f(x) 函数，确认其是否满足单调性。

   如果不满足单调性，可能是 f(x) 函数设计错了，但更有可能是本题无法使用二分答案。

2. 在给定 x 的情况下，结合其他算法，计算出 f(x)。

3. 确定答案上下界，然后二分 x，并用 f(x) 检验即可。

思路

我们试一下上述办法好不好用。

设 f(x) 表示 x 次攻击后能否将所有怪物消灭掉。

可以发现该函数满足单调性，前一段全部无法满足，后一段全部可以满足。

所以可以使用二分答案。

在给定 x 的情况写，我们可以 O(n) 求出 f(x) 是否为真。

思路是贪心，直接看代码。

bool chk(int x)
{
    long long cnt = 0, xb = 1ll * x * b;
   //要开 long long 因为 x*b 会爆。
    for (int i = 1; i <= n; i++)
        if (xb < h[i])
        {
            //伤害不够，尝试把一些 b 替换成 a。
            int t = h[i] - xb;
            cnt += ceil(1.0 * t / (a-b));
            if (cnt > x) return false;
        }
    return true;
}

然后，二分答案即可。二分答案和二分差不多。

int FIND(int l, int r)
{
    //没有什么难点，就是模版。
    while (l < r)
    {
        int mid = l + r >> 1;
        if (chk(mid)) r = mid;
        else l = mid+1;
    }
    return r;
}

另外，注意到 h 数组元素最大 10^9，所以令 l = 1, r = 10^9 二分即可。

完整代码

#include <cstdio>
#include <iostream>
#include <cmath>
#define N 100005
using namespace std;
typedef long long LL;
int n, a, b, h[N];
bool chk(int x)
{
    LL cnt = 0, xb = 1ll * x * b;
    for (int i = 1; i <= n; i++)
        if (xb < h[i])
        {
            int t = h[i] - xb;
            cnt += ceil(1.0 * t / (a-b));
            if (cnt > x) return false;
        }
    return true;
}
int FIND(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (chk(mid)) r = mid;
        else l = mid+1;
    }
    return r;
}
int main()
{
    scanf("%d%d%d", &n, &a, &b);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    printf("%d", FIND(1, 1e9+5));
   //实际上 1e9 就足够了。开大一丢丢保险。
    return 0;
}

希望能帮助到大家！