跳转至

Meeting on the Line

原题链接

题意

有 \(n\) 个人要到一个地方集合，每人要从 \(x[i]\) 出发，出发前要打扮 \(t[i]\) 分钟，走一单位的距离要花费 \(1\) 时间，求最合适的集合的位置,使得集合所需的时间最少。

⭐rating: 1600

我们可以二分集合所需要的最小时间 \(T\)，如果在 \(T\) 时间内所有人可以到达集合点，那么对于 \(\forall x>0\)，在 \(T+x\) 的时间内都可以到达该集合点，因此具有二段性，可以进行二分搜索。

如何进行二分查找？第 \(i\) 个人在 \(T\) 时间内可以到达的区间为 \([x_i-(T-t_i),x_i+(T-t_i)]\)。记 \(p\) 为所有人可到达区间的左端点的最大值，\(q\) 为所有人可到达区间的右端点的最小值。当 \(p \le q\) 时，\(T\) 为有效答案，此时可以确定答案为 \(p\)，可以证明如果时间 \(T\) 为最小的集合时间时，\(p \equiv q\)。

时间复杂度为 \(O(n\log 10^{15})\)

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<double> x(n), t(n);
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int i = 0; i < n; i++) cin >> t[i];

    double l = 0, r = 1e9;
    double ans = -1;
    while (r - l > 1e-6) {
        double mid = (l + r) / 2;
        double p = 0, q = 1e9;
        bool ok = true;
        for (int i = 0; i < n && ok; i++) {
            if (t[i] > mid) {
                ok = false;
                break;
            }

            p = max(p, x[i] - (mid - t[i]));
            q = min(q, x[i] + (mid - t[i]));
            if (p > q) {
                ok = false;
                break;
            }
        }

        if (ok) {
            r = mid;
            ans = p;
        } else l = mid;
    }

    cout << fixed << setprecision(6) << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

分析2 线性

我们可以注意到对于每个人，他们可以到达的区间为：

\[[x_i-(T-t_i),x_i+(T-t_i)] \rightarrow [x_i+t_i-T,x_i-t_i+T]\]

对所有的左端点取最大，右端点取最小，我们可以得到：

\(l=max(x_i+t_i-T)=max(x_i+t_i)-T\)

\(r=min(x_i-t_i+T)=min(x_i-t_i)+T\)

令 \(a=max(x_i+t_i),b=min(x_i-t_i)\)。

则区间的交集为 \([a-T,b+T]\)，因为可以证明，当 \(T\) 最小时，\(a-T=b+T\)。

因此可以求得 \(T=\dfrac{a-b}{2}\)。此时的集结点的位置为 \(a-T=a-\dfrac{a-b}{2}=\dfrac{a+b}{2}\)。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<double> x(n), t(n);
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int i = 0; i < n; i++) cin >> t[i];

    double a = 0, b = 1e9;
    for (int i = 0; i < n; i++) {
        a = max(a, x[i] + t[i]);
        b = min(b, x[i] - t[i]);
    }

    cout << fixed << setprecision(6) << (a + b) / 2 << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}
回到页面顶部