CodeForces 967C Stairs and Elevators 【二分】

发表于 | 更新于 | 分类于

题目大意：

在一个n层高的楼层里，有m块呈直线连在一起的区域，有cl个楼梯和ce个电梯分别在 $a_1$ ~ $a_{cl}$ 和 $b_1$ ~ $b_{ce}$的位置上，从这个位置可以上到上一层楼或者下一层楼。楼梯1s可以上|下一层楼，电梯1s可以上|下$\leq$ v个楼层，从一块到相邻的一块也需要1s的时间。有q个询问，问最少经过多少时间可以从$x1, y1$到达$x2, y2$。

解题思路：

首先想到的是看走楼梯和走电梯哪个时间最少。如果走楼梯，可以走靠近当前位置的左边最近的或者右边最近的，其他同方向位置的楼梯花费的时间一定大于等于这两个位置。电梯同理。
接下来就是找位置了。找这4个位置的时候，因为给出的电梯/楼梯位置是升序的，所以可以用二分查找。一开始写的是分别二分查这4个位置，后来发现只要查两个位置就好了，比如查电梯的第一个$\geq$y1的位置后，另一个要找的位置就是这个位置左边的那个(如果存在的话)。
【注意：】这里有个细节问题不要忽略，就是两位置在一层楼的时候，这时既不需要走楼梯也不需要走电梯。

Mycode(手写二分)：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 1e5+5;

int n, m, c1, c2, v;
int a1[MAX], a2[MAX];
int stx, sty, enx, eny, tem;
int main()
{
    cin >> n >> m >> c1 >> c2 >> v;
    for(int i = 0; i < c1; ++i)
        cin >> a1[i];
    for(int i = 0; i < c2; ++i)
        cin >> a2[i];
    a2[c2] = a1[c1] = 1e9;

    int t;
    cin >> t;
    while(t--)
    {
        int res = 1e9;
        cin >> stx >> sty >> enx >> eny;
        if(stx == enx)
        {
            res = abs(sty - eny);
            cout << res << endl;
            continue;
        }
        int l, r, m, pos;

        if(c1)
        {
            pos = -1, l = 0, r = c1;
            while(l <= r)
            {
                m = (l + r) >> 1;
                if(a1[m] >= sty)
                {
                    r = m - 1;
                    pos = m;
                }
                else
                    l = m + 1;
            }
            if(pos != -1)
            {
                tem = abs(sty - a1[pos]);
                tem += abs(eny - a1[pos]);
                tem += abs(stx - enx);
                res = min(res, tem);
            }

//        cout << pos << "  " << l << "  " << r << "  " <<tem << "   " << res << endl;

            pos = -1, l = 0, r = c1;
            while(l <= r)
            {
                m = (l + r) >> 1;
                if(a1[m] <= sty)
                {
                    l = m + 1;
                    pos = m;
                }
                else
                    r = m - 1;
            }
            if(pos != -1)
            {
                tem = abs(sty - a1[pos]);
                tem += abs(eny - a1[pos]);
                tem += abs(stx - enx);
                res = min(res, tem);
            }
        }

//        cout << pos << "  " << l << "  " << r << "  " <<tem << "   " << res << endl;

        if(c2)
        {
            pos = -1, l = 0, r = c2;
            while(l <= r)
            {
                m = (l + r) >> 1;
                if(a2[m] >= sty)
                {
                    r = m - 1;
                    pos = m;
                }
                else
                    l = m + 1;
            }
            if(pos != -1)
            {
                tem = abs(sty - a2[pos]);
                tem += abs(eny - a2[pos]);
                int tt = abs(stx - enx);
                tem += tt / v;
                if(tt % v)
                    tem++;
                res = min(res, tem);
            }

//        cout << pos << "  " << l << "  " << r << "  " <<tem << "   " << res << endl;


            pos = -1, l = 0, r = c2;
            while(l <= r)
            {
                m = (l + r) >> 1;
                if(a2[m] <= sty)
                {
                    l = m + 1;
                    pos = m;
                }
                else
                    r = m - 1;
            }
            if(pos != -1)
            {
                tem = abs(sty - a2[pos]);
                tem += abs(eny - a2[pos]);
                int tt = abs(stx - enx);
                tem += tt / v;
                if(tt % v)
                    tem++;
                res = min(res, tem);
            }
        }
//        cout << pos << "  " << l << "  " << r << "  " <<tem << "   " << res << endl;

        cout << res << endl;
    }
    return 0;
}

Mycode(stl二分):

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 1e5+5;

int n, m, cl, ce, v;
int a1[MAX], a2[MAX];
int stx, sty, enx, eny, tem, res;
int main()
{
    scanf("%d%d%d%d%d",&n,&m,&cl,&ce,&v);
    for(int i = 0; i < cl; ++i)
        scanf("%d",&a1[i]);
    for(int i = 0; i < ce; ++i)
        scanf("%d",&a2[i]);
    a1[cl] = a2[ce] = 1e9;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        res = 1111111111;
        scanf("%d%d%d%d",&stx,&sty,&enx,&eny);
        if(stx == enx)
            res = abs(sty - eny);
        else
        {
            if(cl > 0)
            {
                int pos = lower_bound(a1, a1+cl, sty) - a1;
                if(a1[pos] != 1e9)
                {
                    tem = 0;
                    tem += abs(sty-a1[pos]);
                    tem += abs(eny-a1[pos]);
                    tem += abs(stx-enx);
                    res = min(res, tem);
                }
                if(pos > 0)
                {
                    --pos;
                    tem = 0;
                    tem += abs(sty-a1[pos]);
                    tem += abs(eny-a1[pos]);
                    tem += abs(stx-enx);
                    res = min(res, tem);
                }
            }
            if(ce > 0)
            {
                int pos = lower_bound(a2, a2+ce, sty) - a2;
                if(a2[pos] != 1e9)
                {
                    tem = 0;
                    tem += abs(sty-a2[pos]);
                    tem += abs(eny-a2[pos]);
                    tem += ceil((double)abs(stx-enx)/v);
                    res = min(res, tem);
                }
                if(pos > 0)
                {
                    --pos;
                    tem = 0;
                    tem += abs(sty-a2[pos]);
                    tem += abs(eny-a2[pos]);
                    tem += ceil((double)abs(stx-enx)/v);
                    res = min(res, tem);
                }
            }
        }
        printf("%d\n", res);
    }
    return 0;
}
Donate comment here
0%