# # 二分查找

## # 练习题

### #SPOJ - AGGRCOW (opens new window)

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, c;
cin >> n >> c;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
sort(a.begin(), a.end());
int lo = 1, hi = a.back() - a.front();
while (lo <= hi) {
int mid = (lo + hi) >> 1;
int cnt = 0, left = 0;
for (int i = 1; i < n - 1; ++i) {
if (a[n - 1] - a[i] < mid)
break;
if (a[i] - a[left] >= mid) {
cnt++;
left = i;
}
}
if (cnt >= c - 2)
lo = mid + 1;
else
hi = mid - 1;
}
cout << hi << endl;
}
}

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

### #SNSS-2020 R2 - Meeting with readers (opens new window)

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
struct Author {
ll l, r, w, idx;
bool operator<(const Author &other) const {
return l < other.l || (l == other.l && r > other.r);
}
};
int main() {
int n;
cin >> n;
vector<Author> a;
for (int i = 0; i < n; ++i) {
ll l, r, w;
cin >> l >> r >> w;
a.push_back(Author{l, r, w, i + 1});
}
sort(a.begin(), a.end());
ll L, R;
cin >> L >> R;
ll lo = 0, hi = 1e18;
while (lo <= hi) {
ll mid = lo + (hi - lo) / 2;
ll l = -1, r = -1;
bool ok = true;
for (int i = 0; i < n; ++i) {
if (a[i].w > mid)
continue;
if (r < a[i].l)
l = a[i].l;
r = max(r, a[i].r);
if (r >= R)
break;
}
if (l != -1 && l <= L && r >= R)
hi = mid - 1;
else
lo = mid + 1;
}
if (lo >= 1e18) {
cout << -1;
return 0;
}
vector<int> ans;
for (int i = 0; i < n; ++i)
if (a[i].w <= lo && a[i].l < R)
ans.emplace_back(a[i].idx);
cout << ans.size() << endl;
for (int i : ans)
cout << i << " ";
}

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

### #LC1482 - 制作 m 束花所需的最少天数 (opens new window)

typedef long long ll;

class Solution {
public:
int minDays(vector<int>& bloomDay, int m, int k) {
int n = bloomDay.size();
if (n / k < m)
return -1;
int l = 1, r = 1e9;
auto check = [&](int x) {
vector<bool> flower(n);
for (int i = 0; i < n; ++i)
if (bloomDay[i] <= x)
flower[i] = true;
int bunch = 0, curr = 0;
for (int i = 0; i < n; ++i) {
if (flower[i])
curr++;
else {
bunch += curr / k;
curr = 0;
}
}
bunch += curr / k;
return bunch;
};
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid) < m)
l = mid + 1;
else
r = mid - 1;
}
return l;
}
};

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

### #BS - K-Distinct-Groups (opens new window)

#include "solution.hpp"
using namespace std;

class Solution {
public:
int solve(vector<int>& counts, int k) {
int l = 1, r = INT_MAX;
while (l <= r) {
int mid = l + (r - l) / 2;
int tot = 0;
for (int count : counts)
tot += min(mid, count);
if (tot >= (long long)mid * k)
l = mid + 1;
else
r = mid - 1;
}
return r;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

var('x')
g = Graphics()
g += plot(x-3, (x,0,3))
g += plot(x+3, (x,-3,0))
g += plot(3, (x,0,3))
g += plot(-3, (x,-3,0))
g += line([(3,0),(3,3)])
g += line([(-3,-3),(-3,0)])
g.show()

1
2
3
4
5
6
7
8
9

#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());
auto check = [&](int l, bool output) {
int xl = 0, xr = 5e5, yl = 0, yr = 5e5, zl = -5e5, zr = 5e5;
for (auto p : vs) {
xl = max(xl, p.first - l);
xr = min(xr, p.first + l);
yl = max(yl, p.second - l);
yr = min(yr, p.second + l);
zl = max(zl, p.first - p.second - l);
zr = min(zr, p.first - p.second + l);
}
if (xl > xr || yl > yr || zl > zr)
return false;
int zl1 = xl - yr, zr1 = xr - yl;
if (output) {
// To avoid (0, 0), we choose right endpoint for both x and y.
int x = min(xr, zr + yr);
int y = min(yr, x - zl);
string s(x, 'B'), t(y, 'N');
printf("%s", (s + t).c_str());
}
return max(zl, zl1) <= min(zr, zr1);
};
int lo = 0, hi = 1e6;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (check(mid, false))
hi = mid - 1;
else
lo = mid + 1;
}
printf("%d\n", lo);
check(lo, true);
}
};

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