hyz's blog
0%

CF 967C: Stairs and Elevators

发表于

题意

题意很简单，略:)

分析

首先注意到楼梯、电梯是垂直连通整栋楼的，所以，我们没必要多次走楼梯或乘坐电梯，最多只要一次。因此，我们可以找离出发点y1最近的两个楼梯和两个电梯，这可以通过二分来实现，然后分别计算时间，取min即可。需要注意的是，楼层相同时不需要走楼梯或乘坐电梯。

代码

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

#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

int n, m, cl, ce, v, a[N], b[N], q, x1, y_1, x2, y2;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(cin >> n >> m >> cl >> ce >> v) {
        for(int i = 0; i < cl; i++)
            scanf("%d", a + i);
        for(int i = 0; i < ce; i++)
            scanf("%d", b + i);
        scanf("%d", &q);
        while(q--) {
            scanf("%d%d%d%d", &x1, &y_1, &x2, &y2);
            if(x1 == x2) {
                printf("%d\n", abs(y_1 - y2));
                continue;
            }
            int ans = INF;
            int p = lower_bound(a, a+cl, y_1) - a;
            if(p != cl)
                ans = min(ans, abs(a[p] - y_1) + abs(x2 - x1) + abs(a[p] - y2));
            if(--p >= 0)
                ans = min(ans, abs(a[p] - y_1) + abs(x2 - x1) + abs(a[p] - y2));
            p = lower_bound(b, b+ce, y_1) - b;
            if(p != ce)
                ans = min(ans, abs(b[p] - y_1) + (int)ceil(1.0*abs(x2 - x1) / v) + abs(b[p] - y2));
            if(--p >= 0)
                ans = min(ans, abs(b[p] - y_1) + (int)ceil(1.0*abs(x2 - x1) / v) + abs(b[p] - y2));
            printf("%d\n", ans);
        }
    }
    return 0;
}