Three Base Stations
Created by LXC on Thu May 4 00:56:54 2023
https://codeforces.com/problemset/problem/51/C
ranting: 1800
tag: binary search, greedy
题意
有n个村庄在一条数轴上排列
给出n个数字代表n个村庄的位置
现在要建立三个基站，三个基站的信号强度都是d，当在x位置建立基站时，信号覆盖范围在[x-d,x+d]。
求最小的信号强度，以及三个基站的位置，使得所有村庄可以被信号覆盖。
题解
我们二分答案。确定信号强度。
然后贪心，如果所有村庄分成长度不超过2d的段数不超过3则说明当前的信号强度可行。显然大于这个信号强度的分段数也是不超过3的。所以可以二分从小到大找到第一个满足的d。
代码
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
| #include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;
void sol() {
int n;
cin >> n;
vector<ll> v(n);
for (ll& i : v)
cin >> i;
sort(v.begin(), v.end());
double l = 0, r = v[n - 1] - v[0];
while (r - l >= 1e-7) {
double m = (r - l) / 2 + l;
int p = 0, c = 0;
for (int i = 0; i < n; i++) {
if (v[i] - v[p] > m)
p = i, c++;
}
if (c < 3) {
r = m;
} else {
l = m;
}
}
cout.precision(6);
cout << fixed << r / 2 << "\n";
int p = 0, c = 0;
for (int i = 0; i < n; i++) {
if (v[i] - v[p] > r) {
cout << (v[i - 1] + v[p]) / 2.0 << " ";
c++;
p = i;
}
}
for (int i = c; i < 3; i++) {
cout << (v[n - 1] + v[p]) / 2.0 << " ";
}
cout << "\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;
}
|