今天寫了這題才知道原來浮點數二分搜要這樣寫。
原本我以為應該是要根據他想要的浮點數誤誤差當作 eps，然後寫成這樣
1
2
3
| while (r - l > eps) {
do binary search
}
|
但那樣的話會 TLE，因為 r - l 的精度誤差有可能導致這個 while 會變成一個無窮迴圈，就是其實他已經達到 eps 了但是減起來大於。
所以應該要根據你的範圍跟他要的浮點數誤差來估計要砍半幾次，砍一次的精度是 0.5，所以砍 10 次的話大概會是 1e-3，所以根據你要的範圍 / 浮點數誤差 / 3 * 10 大概就是你要砍半的次數。
順便附上這題我的 code，我覺得想法不難只是需要知道浮點數二分搜怎麼寫而已。
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define SZ(a) (int)(a).size()
#define ALL(v) (v).begin(), (v).end()
#define X first
#define Y second
#ifdef debug
void trace_() { cerr << "\n"; }
template <typename T1, typename... T2>
void trace_(T1 t1, T2... t2) {
cerr << ' ' << t1;
trace_(t2...);
}
#define trace(...) cerr << "[" << #__VA_ARGS__ << "] :", trace_(__VA_ARGS__);
#else
#define trace(...) 49
#endif
void solve() {
int n; cin >> n;
vector<double> p(n), v(n);
for (double &x : p) cin >> x;
for (double &x : v) cin >> x;
auto chk = [&](double x) {
// check if everyone can meet at a point after x seconds
double lb = -1, ub = 1e9 + 1;
for (int i = 0; i < n; i++) {
lb = max(lb, p[i] - v[i] * x);
ub = min(ub, p[i] + v[i] * x);
}
if (lb <= ub) return true;
return false;
};
double l = 0, r = 6e14;
int C = 100;
while (C--) {
double m = (l + r) / 2.0;
if (chk(m)) r = m;
else l = m;
}
cout << fixed << setprecision(15) << r << "\n";
}
/*
CheckList:
1. long long
2. mod
3. template
4. input/output format/content
5. test sample input/output
*/
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
return 0;
}
|