When to Use Binary Search on Answer

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Given stall positions and number of cows, place cows to maximize the minimum distance
5
// between any two placed cows.
6
// Feasibility: for a candidate distance d, greedily place cows and check if we can place at least C cows.
7
8
static bool canPlace(const vector<long long>& pos, int C, long long d) {
9
    long long last = pos[0];
10
    int placed = 1; // place first cow at the first stall
11
    for (size_t i = 1; i < pos.size(); ++i) {
12
        if (pos[i] - last >= d) {
13
            last = pos[i];
14
            ++placed;
15
            if (placed >= C) return true; // early success
16
        }
17
    }
18
    return false;
19
}
20
21
int main() {
22
    ios::sync_with_stdio(false);
23
    cin.tie(nullptr);
24
25
    int N, C;
26
    if (!(cin >> N >> C)) return 0;
27
    vector<long long> pos(N);
28
    for (int i = 0; i < N; ++i) cin >> pos[i];
29
30
    sort(pos.begin(), pos.end()); // O(N log N)
31
32
    long long l = 0; // minimum possible distance
33
    long long r = pos.back() - pos.front(); // maximum possible distance
34
35
    // Maximization: upper-bound template (bias mid up)
36
    while (l < r) {
37
        long long mid = l + (r - l + 1) / 2; // (l + r + 1) / 2 safely
38
        if (canPlace(pos, C, mid)) {
39
            l = mid; // feasible: try larger distance
40
        } else {
41
            r = mid - 1; // infeasible: reduce distance
42
        }
43
    }
44
45
    cout << l << "\n"; // largest minimum distance
46
    return 0;
47
}
48

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Each machine i makes one item every t[i] time units. Machines work in parallel.
5
// Find the minimum time T so that total items produced in T is at least K.
6
// Feasibility: sum_{i} floor(T / t[i]) >= K.
7
8
static bool enough(long long T, const vector<long long>& t, long long K) {
9
    __int128 produced = 0; // prevent overflow when summing
10
    for (long long x : t) {
11
        produced += T / x;
12
        if (produced >= K) return true; // early exit if already enough
13
    }
14
    return produced >= K;
15
}
16
17
int main() {
18
    ios::sync_with_stdio(false);
19
    cin.tie(nullptr);
20
21
    int n; long long K;
22
    if (!(cin >> n >> K)) return 0;
23
    vector<long long> t(n);
24
    for (int i = 0; i < n; ++i) cin >> t[i];
25
26
    long long min_t = *min_element(t.begin(), t.end());
27
    long long l = 0;
28
    long long r = min_t * K; // upper bound: fastest machine alone produces K items
29
30
    // Minimization: lower-bound template
31
    while (l < r) {
32
        long long mid = l + (r - l) / 2;
33
        if (enough(mid, t, K)) {
34
            r = mid; // feasible time, try to reduce
35
        } else {
36
            l = mid + 1; // infeasible, need more time
37
        }
38
    }
39
40
    cout << l << "\n"; // minimum time to make K items
41
    return 0;
42
}
43

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Given array a and integer m, split a into at most m non-empty contiguous subarrays
5
// to minimize the maximum subarray sum. Feasibility: with capacity cap, greedily form
6
// subarrays whose sums do not exceed cap; count how many are needed.
7
8
static bool canSplit(const vector<long long>& a, int m, long long cap) {
9
    int used = 1; // start with one subarray
10
    long long cur = 0;
11
    for (long long x : a) {
12
        if (x > cap) return false; // single element exceeds cap => impossible
13
        if (cur + x <= cap) {
14
            cur += x;
15
        } else {
16
            ++used;
17
            cur = x;
18
            if (used > m) return false; // too many subarrays needed
19
        }
20
    }
21
    return true; // within m subarrays
22
}
23
24
int main() {
25
    ios::sync_with_stdio(false);
26
    cin.tie(nullptr);
27
28
    int n, m;
29
    if (!(cin >> n >> m)) return 0;
30
    vector<long long> a(n);
31
    for (int i = 0; i < n; ++i) cin >> a[i];
32
33
    long long l = *max_element(a.begin(), a.end()); // at least the largest element
34
    long long r = accumulate(a.begin(), a.end(), 0LL); // at most the total sum
35
36
    // Minimization: lower-bound template
37
    while (l < r) {
38
        long long mid = l + (r - l) / 2; // candidate capacity
39
        if (canSplit(a, m, mid)) {
40
            r = mid; // feasible capacity; try lower
41
        } else {
42
            l = mid + 1; // infeasible; need larger capacity
43
        }
44
    }
45
46
    cout << l << "\n"; // minimal possible largest subarray sum
47
    return 0;
48
}
49