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; }
|