HDU 5935 Car 题解
题目大意
给定位移轴上的 \(n\)个点，一个人从 \(x=0\) 原点出发，给定的位移轴上的点到达的时间未知，但一定是整数时刻，Ruins 的速度是一个不降的实数曲线，问最短经过多少时间可以走完。
题解
由于时间要短，所以速度要尽可能大，我们考虑速度最快的最后，由于每两个给定位置经过的时间差最小只能是 \(1\)（要求在整时刻上），于是我们贪心地把最后的速度 \(\displaystyle v=\frac{a[i]-a[i-1]}{1}\)，然后尝试着按这个速度往前走。
由于要求必须走整时刻到给定点，如果以当前速度可以整倍数的走完，则直接走就可以，若不能，则意味着我们必须改变速度，由于速度一定要降低，先设一个准确的实数时间 \(\displaystyle t=\frac{\Delta s}{v}\)，然后对 \(t\) 下取整，由于下取整后刚好走不完，我们让新的速度 \(\displaystyle v'=\frac{\Delta s}{t+1}\)（即希望把速度稍微放慢一点，使得恰好在整时刻走完），即取到尽可能大的合法速度，以此类推一直走到 \(0\) 即可。
代码
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
|
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename _Tp>
void read(_Tp &a, char c = 0, int f = 1) {
for(c = getchar(); !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar()); a *= f;
}
template <typename _Tp>
void write(_Tp a) {
if(a < 0) putchar('-'), a = -a;
if(a > 9) write(a / 10); putchar(a % 10 + '0');
}
const int N = 1e5 + 5;
const ld eps = 1e-9;
int n;
int a[N];
int main() {
int T;
read(T);
for(int _T = 1; _T <= T; _T++) {
ll ans = 0;
read(n);
for(int i = 1; i <= n; i++) {
read(a[i]);
}
ld v = -1;
for(int i = n; i >= 1; i--) {
ld ds = a[i] - a[i - 1];
if(v < 0) {
v = ds;
ans++;
} else {
ll t = ds / v;
ld _s = v * t;
if(fabs(ds - _s) < eps) {
ans += t;
} else {
v = ds / (t + 1);
ans += t + 1;
}
}
}
printf("Case #%d: ", _T), write(ans), putchar('\n');
}
return 0;
}
|