Tram
Created by LXC on Wed May 10 00:02:34 2023
https://codeforces.com/problemset/problem/746/C
ranting: 1600
tag: constructive algorithms, implementation, math
题意
现有一条数轴，从0到s。
然后有一辆列车从p点以速度为每t1秒移动一米，往方向为d（d为-1向0走，d为1向s走）移动。
当移动到尽头时改变方向。
现在有个人想要从x1到x2，这个人可以移动的速度时每t2秒移动1米。中途如果与列车相遇可以立刻上车或下车。
求从x1到x2的最短的时间
题解
首先如果车速比人速度慢没必要打车。
然后在车速大于人速度的情况下。
可以考虑当前p在首先经过x1的情况下再经过x2的时间u。
再考虑人直接从x1走到x2的时间v。
显然答案就是u和v的最小值。
这需要分类讨论，要考虑车x1和x2的大小，车与x1或x2的位置关系，以及车初始时的移动方向。
代码
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
|
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;
void sol() {
int s, x1, x2, t1, t2, p, d;
cin >> s >> x1 >> x2 >> t1 >> t2 >> p >> d;
int a = abs(x2 - x1) * t2;
if (t1 > t2) {
cout << a << "\n";
return;
}
if (x1 < x2) {
if (d == 1) {
if (p <= x1) {
a = min(a, (x2 - p) * t1);
} else {
a = min(a, (s - p + s + x2) * t1);
}
} else {
a = min(a, (p + x2) * t1);
}
} else {
if (d == -1) {
if (p >= x1) {
a = min(a, (p - x2) * t1);
} else {
a = min(a, (p + s + s - x2) * t1);
}
} else {
a = min(a, (s - p + s - x2) * t1);
}
}
cout << a << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef SINGLE_INPUT
int t;
cin >> t;
while (t--) {
sol();
}
#else
sol();
#endif
return 0;
}
|