P6397 [COI2008] GLASNICI

一条直线上有 n 个信使，将他们按照从左至右的顺序以 1 至 n 编号。换句话说，设 i 号信使的的坐标为 d_i，则对于 1 \leq i \lt n， d_i \leq d_{i + 1}。

信使传递一条消息的方法如下：

  • 在任意时刻（不一定是整数时刻），任一信使（无论是否已知消息）都可以自由选择向左移动或者向右移动或者原地不动。其移动的速度为每秒 1 单位长度。
  • 当两个信使相距不超过一给定实数 k 时，双方可以进行消息传递，也即如果两人中有一人已知该消息，则两人都知道了该消息。消息传递是瞬间发生的，不消耗时间。

现在 1 号信使得到了一条消息，请求出最小的让所有信使都得到该消息的用时。

1 \leq n \leq 10^5,0 \leq k \leq 10^6

解题思路

很巧妙的思维题。

首先把问题转化一下,对于一个点 x_i,存在点能覆盖到 x_i 的范围为 [x_i-k,x_i+k]。

可以画个图加以理解。

我们发现，这个用时肯定满足单调性，所以我们考虑二分。接着考虑边界，左边界肯定为 0，也就是所有点互相可以传信息的情况。右边界为 x_n - x_1 - k 代表着 x_1 要一直走到 x_n-k 的位置。

关于实数域上的二分，我们可以这么写.

const double eps = 1e-6;//输出k位小数，eps最好设为10^(-k-2)
double l = 0.0,r = pos[n] - k - pos[1];
while (l + eps < r) {
    double mid = (l + r) / 2;
    if (check(mid)) r = mid;
    else l = mid;
}

接着考虑 check 怎么写。我们可以想一下两个点是如何相遇的：当前点 i 往右走， 点 i+1 往左走。注意到题目中是所有点都可以移动，所以为了保持相对位置不变，我们对于后面的点同时也要向左走。

结合图理解更佳。

所以我们可以弄一个指针 now，表示当前能到达的最远地方。在最开始，我们贪心地让 now = x_1 + k，接下来有两种情况：

  1. now + k \geq x_{i+1} 这种情况就贪心的让 now = now + k
  2. now + k < x_{i+1} 这种情况我们没有办法，只能让 now = x_i + k
  3. now < x_i - k - mid 这样无论怎么都到达不了了， mid 就肯定不能取到。

变成代码就是

bool check(double x) {
    double now = pos[1] + x;//初始化
    for (int i = 2;i <= n;++i) {
        if (pos[i] - k - now > x) return 0;//情况3
        now = min(now + k,pos[i] + x);//情况1和情况2
    }
    return 1;
}

所以我们就在 O(n \log d) 的时间内解决了本题。

代码

#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
#define ri register int

const int N = 100010;
const double eps = 1e-6;

double pos[N],k;

int n;

bool check(double x) {
    double now = pos[1] + x;
    for (int i = 2;i <= n;++i) {
        if (pos[i] - k - now > x) return 0;
        now = min(now + k,pos[i] + x);
    }
    return 1;
}

signed main() {
    scanf("%lf\n%d",&k,&n);
    for (int i = 1;i <= n;++i) scanf("%lf",&pos[i]);
    double l = 0.0,r = pos[n] - k - pos[1];
    while (l + eps < r) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    printf("%.4f",l);
    return 0;
}