# # 三分查找

## # 练习题

### #CF1394C - Boboniu and String (opens new window)

#include <cstdio>
#include <iostream>
#include <set>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
set<pair<int, int>> s;
for (int i = 0; i < n; ++i) {
string t;
cin >> t;
int b = 0;
for (char c : t)
b += c == 'B';
s.insert({b, t.size() - b});
};
vector<pair<int, int>> vs(s.begin(), s.end());
int m = vs.size();
int tb = 0, tn = 0;
for (auto p : vs)
tb = max(tb, p.first), tn = max(tn, p.second);
auto calc = [&](int B, int N) {
int dist = 0;
for (auto &[b, n] : vs) {
if ((ll)(b - B) * (n - N) >= 0)
dist = max(dist, max(abs(b - B), abs(n - N)));
else
dist = max(dist, abs(b - B) + abs(n - N));
}
return dist;
};
auto query = [&](int b, int lo) {
int hi = tn;
while (lo <= hi) {
int ml = lo + (hi - lo) / 3, mr = hi - (hi - lo) / 3;
int ql = calc(b, ml), qr = calc(b, mr);
if (ql >= qr)
lo = ml + 1;
if (ql <= qr)
hi = mr - 1;
}
int extreme = (lo + hi) / 2;
int dist = calc(b, extreme);
return make_pair(extreme, dist);
};
int lo = 1, hi = tb;
while (lo <= hi) {
int ml = lo + (hi - lo) / 3, mr = hi - (hi - lo) / 3;
int ql = query(ml, 0).second, qr = query(mr, 0).second;
if (ql >= qr)
lo = ml + 1;
if (ql <= qr)
hi = mr - 1;
}
int ansb = (lo + hi) / 2;
auto [ansn, dist] = query(ansb, 0);
auto [ansn2, dist2] = query(0, 1);
if (dist2 < dist) {
dist = dist2;
ansn = ansn2;
ansb = 0;
}
printf("%d\n", dist);
string ans = string(ansb, 'B') + string(ansn, 'N');
printf("%s\n", ans.c_str());
}
};

int main() {
Solution solution = Solution();
solution.solve();
}

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

### #LC1515 - 服务中心的最佳位置 (opens new window)


class Solution {
public:
double getMinDistSum(vector<vector<int>>& positions) {
double eps = 1e-7;
auto dist = [&](double xc, double yc) {
double ans = 0;
for (const auto& pos: positions) {
ans += sqrt((pos[0] - xc) * (pos[0] - xc) + (pos[1] - yc) * (pos[1] - yc));
}
return ans;
};
auto query = [&](double cx) {
double l = 0, r = 100;
while (r - l > eps) {
double ml = l + (r - l) / 3, mr = r - (r - l) / 3;
double dl = dist(cx, ml), dr = dist(cx, mr);
if (dl > dr)
l = ml;
else
r = mr;
}
return dist(cx, l);
};
double l = 0, r = 100, ans = 1e9;
while (r - l > eps) {
double ml = l + (r - l) / 3, mr = r - (r - l) / 3;
double dl = query(ml), dr = query(mr);
if (dl > dr)
l = ml;
else
r = mr;
ans = min(ans, min(dl, dr));
}
return ans;
}
};

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