AT1330 题解

前言

题目传送门！

更好的阅读体验？

这一题内部比赛时考到了，个人觉得是一道二分答案好题。

本题时间很宽松，导致 (O(n log^2 n)) 的代码可以跑过去。

但是，我内部比赛的时限是 (1) 秒，这就导致需要 (O(n log n)) 的代码了。

思路一

显然是一道二分答案题目。

二分答案老套路，设 (f(x)) 表示 (x) 是否能作为答案，易得 (f(x)) 单调递增。

所以，可以使用二分答案。

重点是 (texttt{check()}) 函数如何编写，我们可以使用贪心的思想。

对于每个气球，我们可以得出，打掉它的时间 (t_i) 不得超过 (leftlfloordfrac{x - h_i}{s_i}rightrfloor)。

我们可以对 (t) 数组从小到大排序。

对于 (0 le i < n)，我们从贪心的角度思考。如果 (i > t_i)，说明已经无法满足 (x) 了。

如果全部都符合，说明 (t) 数组的攻击方式就是一种合法的方案，那么 (x) 这个答案是可行的。

(texttt{check()}) 函数代码如下。

typedef long long LL;
int n, h[N], s[N];
LL t[N];
bool chk(LL x)
{
    for (int i = 1; i <= n; i++)
    {
        //如果时刻 0 打掉它都无法满足，立刻叉掉。
        if (x < h[i]) return false;
        t[i-1] = (x - h[i]) / s[i]; //为了方便处理，下标从 0 开始。
    }
    sort(t, t+n);
    for (int i = 0; i < n; i++)
        if (t[i] < i)
            return false;
    return true;
}

这里的时间复杂度是 (O(n log n))，加上二分的板子，需要 (O(n log^2 n))。

可以通过此题，但还可以优化吗？

思路二

时间复杂度瓶颈在于排序，如果想降到 (O(n))，就需要使用 (O(n)) 的排序算法。

你想到什么方法了？对，桶排序！

我们发现，当 (t_i ge n)，说明任意时刻打掉它都是可行的，所以可以忽略不计。

这样，桶数组空间就符合了。

需要注意，(texttt{check()}) 开始前要初始化桶。

bool chk(LL x)
{
    memset(box, 0, sizeof(box));
    for (int i = 1; i <= n; i++)
    {
        //在主程序外面保证了 x 大于等于 h[i]，就不需要担心了。
        LL t = (x - h[i]) / s[i];
        if (t < n) box[t]++;
    }
    int cur = 0;
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= box[i]; j++)
        {
            if (i < cur) return false;
            cur++;
        }
    return true;
}

时间复杂度终于优化成了 (O(n))。

最后，我们补全二分。

LL FIND(LL l, LL r)
{
    //显然是模版，完全没改变。
    while (l < r)
    {
        LL mid = l + r >> 1;
        if (chk(mid)) r = mid;
        else l = mid+1;
    }
    return r;
}
int main()
{
    scanf("%d", &n);
    int maxn = -1;
    for (int i = 1; i <= n; i++) scanf("%d%d", &h[i], &s[i]), maxn = max(maxn, h[i]);
    //从 maxn 开始，保证了 chk() 函数不会出现 x < h[i] 的情况。
    //10^9 + 10^5 * 10^9 近似看成 10^15，毕竟大一点没坏处。
    printf("%lldn", FIND(maxn, 1e15));
    return 0;
}

希望对大家有帮助！
首发：2022-07-02 10:33:00