Binary Search on Answer

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Check if we can place k cows with minimum pairwise distance >= d
5
bool canPlace(const vector<int>& pos, int k, int d) {
6
    int count = 1;                  // place first cow at pos[0]
7
    int last = pos[0];
8
    for (size_t i = 1; i < pos.size(); ++i) {
9
        if (pos[i] - last >= d) {   // greedy: place at earliest valid position
10
            ++count;
11
            last = pos[i];
12
            if (count >= k) return true; // early exit if all placed
13
        }
14
    }
15
    return false;
16
}
17
18
int main() {
19
    ios::sync_with_stdio(false);
20
    cin.tie(nullptr);
21
22
    vector<int> positions = {1, 2, 4, 8, 9};
23
    int k = 3; // number of cows (routers)
24
25
    sort(positions.begin(), positions.end());
26
27
    int lo = 0;                                 // smallest possible distance
28
    int hi = positions.back() - positions.front(); // largest possible distance
29
30
    // We maximize the minimum distance, so use upper-mid to avoid infinite loops
31
    while (lo < hi) {
32
        int mid = lo + (hi - lo + 1) / 2; // upper-mid
33
        if (canPlace(positions, k, mid)) {
34
            lo = mid; // feasible: try a larger distance
35
        } else {
36
            hi = mid - 1; // infeasible: shrink high
37
        }
38
    }
39
40
    cout << "Max minimal distance = " << lo << "\n"; // expected 3 for this data
41
    return 0;
42
}
43

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Check if we can split array into <= m parts with each part sum <= limit
5
bool canSplit(const vector<int>& a, int m, long long limit) {
6
    long long current = 0;
7
    int parts = 1;
8
    for (int x : a) {
9
        if (x > limit) return false; // single element exceeds limit => impossible
10
        if (current + x <= limit) {
11
            current += x;
12
        } else {
13
            ++parts;
14
            current = x;
15
            if (parts > m) return false; // too many parts
16
        }
17
    }
18
    return true;
19
}
20
21
int main() {
22
    ios::sync_with_stdio(false);
23
    cin.tie(nullptr);
24
25
    vector<int> a = {7, 2, 5, 10, 8};
26
    int m = 2;
27
28
    long long lo = *max_element(a.begin(), a.end()); // lower bound on answer
29
    long long hi = accumulate(a.begin(), a.end(), 0LL); // upper bound on answer
30
31
    // We minimize the maximum part sum, so use lower-mid and move hi down on success
32
    while (lo < hi) {
33
        long long mid = lo + (hi - lo) / 2; // lower-mid
34
        if (canSplit(a, m, mid)) {
35
            hi = mid; // feasible: try a smaller maximum sum
36
        } else {
37
            lo = mid + 1; // infeasible: need larger maximum sum
38
        }
39
    }
40
41
    cout << "Minimized largest sum = " << lo << "\n"; // expected 18 for this data
42
    return 0;
43
}
44

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Given machine times t[i], can we produce at least target items within time T?
5
bool canProduce(const vector<long long>& t, long long target, long long T) {
6
    __int128 total = 0; // use wider accumulator to prevent overflow
7
    for (long long ti : t) {
8
        total += T / ti; // items produced by machine i
9
        if (total >= target) return true; // early stop to save time
10
    }
11
    return total >= target;
12
}
13
14
int main() {
15
    ios::sync_with_stdio(false);
16
    cin.tie(nullptr);
17
18
    vector<long long> machines = {2, 3, 7};
19
    long long target = 15;
20
21
    long long lo = 0;
22
    long long fastest = *min_element(machines.begin(), machines.end());
23
    long long hi = fastest * target; // safe upper bound: fastest machine does all
24
25
    while (lo < hi) {
26
        long long mid = lo + (hi - lo) / 2;
27
        if (canProduce(machines, target, mid)) {
28
            hi = mid; // feasible: can we do it faster?
29
        } else {
30
            lo = mid + 1; // infeasible: need more time
31
        }
32
    }
33
34
    cout << "Minimum time = " << lo << "\n"; // prints minimal time to make 'target' items
35
    return 0;
36
}
37

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Check if we can cut at least k pieces of length L from the ropes
5
bool canCut(const vector<double>& ropes, int k, double L) {
6
    if (L <= 0) return true; // trivially true, but we avoid L=0 in search
7
    long long count = 0;
8
    for (double r : ropes) {
9
        count += static_cast<long long>(r / L); // floor(r / L)
10
        if (count >= k) return true; // early exit
11
    }
12
    return false;
13
}
14
15
int main() {
16
    ios::sync_with_stdio(false);
17
    cin.tie(nullptr);
18
19
    vector<double> ropes = {8.02, 7.43, 4.57, 5.39};
20
    int k = 11;
21
22
    double lo = 0.0;
23
    double hi = *max_element(ropes.begin(), ropes.end());
24
25
    // Perform fixed iterations to control precision (epsilon ≈ (hi-lo)/2^iters)
26
    for (int it = 0; it < 70; ++it) { // ~1e-21 relative shrink; plenty for printing 2-6 decimals
27
        double mid = 0.5 * (lo + hi);
28
        if (canCut(ropes, k, mid)) {
29
            lo = mid; // feasible: try longer pieces
30
        } else {
31
            hi = mid; // infeasible: shorten pieces
32
        }
33
    }
34
35
    cout.setf(std::ios::fixed); cout << setprecision(2);
36
    cout << "Max piece length (≈) = " << lo << "\n"; // print with 2 decimals
37
    return 0;
38
}
39