Codeforces 343C Read Time 题解
题意
在一个无限长的线性磁盘上,有$n$个独立的磁头和$m$个需读取的位置$(1\le n,m\le 10^5)$,第$i$个磁头的初始位置为$h_i (1\le h_i\le 10^{10},h_i<h_{i+1})$,第$j$个需读取位置为$p_j (1\le p_j\le 10^{10},p_j<p_{j+1})$,需读取的位置互不相同的。
每一个磁头可以花一个单位时间移动到左边或右边的位置,也可以不动。可以有多个磁头在同一位置。每个磁头可以读取无限多个位置。一个位置被至少一个磁头走过后,它就被读取了。特别,一开始时,$h_i (1\le i\le n)$的位置就被读取过了。
求读取所有需读取位置需要的最少时间。
题解
考虑二分需要的时间。
对于check(time)
函数,每个磁头都有time
单位个时间。
设当前考虑的磁头为第$i$个磁头,设$pos$为 第$i-1$个磁头没有完成的最左边的需读取位置,那么它要在读取$pos$后,尽可能地多读取位置。
确定尽可能向后读取的位置有两种,设走到$pos$后,还剩$r$个单位时间。
先走到$pos$,再用$r$个时间尽可能地多读取位置。
先用$\frac{r}{2}$个时间尽可能地多读取位置(用$\frac{r}{2}$个时间走回来),再走到$pos$。
在$p$中upper_bound(MAX)
后,就可以找到第$i$个磁头没有完成的最左边的需读取位置了。
所以check
函数的时间复杂度是$O(n\log n)$。
Tip: 还有一种方法可以使check
函数的时间复杂度是$O(n)$,具体不再赘述。
程序
1 | // #pragma GCC optimize(2) |