题目传送门!
更好的阅读体验?
这一题内部比赛时考到了,个人觉得是一道二分答案好题。
本题时间很宽松,导致 \(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\) 这个答案是可行的。
\(\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("%lld\n", FIND(maxn, 1e15)); return 0; }
希望对大家有帮助!
首发:2022-07-02 10:33:00