AT1330 题解
liangbowen
·
·
题解
前言
题目传送门！
更好的阅读体验？
这一题内部比赛时考到了，个人觉得是一道二分答案好题。
本题时间很宽松，导致 O(n \log^2 n) 的代码可以跑过去。
但是，我内部比赛的时限是 1 秒，这就导致需要 O(n \log n) 的代码了。
思路一
显然是一道二分答案题目。
二分答案老套路，设 f(x) 表示 x 是否能作为答案，易得 f(x) 单调递增。
所以，可以使用二分答案。
重点是 \texttt{check()} 函数如何编写，我们可以使用贪心的思想。
对于每个气球，我们可以得出，打掉它的时间 t_i 不得超过 \left\lfloor\dfrac{x - h_i}{s_i}\right\rfloor。
我们可以对 t 数组从小到大排序。
对于 0 \le i < n，我们从贪心的角度思考。如果 i > t_i，说明已经无法满足 x 了。
如果全部都符合，说明 t 数组的攻击方式就是一种合法的方案，那么 x 这个答案是可行的。
```cpp
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()}$ 开始前要初始化桶。
```cpp
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)$。
最后，我们补全二分。
```cpp
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("%lld\n", FIND(maxn, 1e15));
return 0;
}
```
希望对大家有帮助！