uniolympiads English

Δυαδική αναζήτηση στην απάντηση

Όταν το «γίνεται με xx;» είναι μονότονο ως προς xx, βρίσκεις το μικρότερο xx που γίνεται σε O(log⁡)O(\log) ελέγχους.

Πότε

Το πρόβλημα ζητά «το ελάχιστο xx ώστε…» ή «το μέγιστο xx ώστε…», και είναι εύκολο να ελέγξεις αν ένα συγκεκριμένο xx αρκεί. Το σήμα είναι η μονοτονία: αν το xx αρκεί, αρκεί και κάθε μεγαλύτερο.

Η ιδέα

Έστω ok(x)\mathrm{ok}(x) που είναι ψευδές, …, ψευδές, αληθές, …, αληθές στο [lo,hi][lo, hi]. Κρατάμε την αναλλοίωτη: όλα κάτω από το lolo είναι ψευδή, όλα πάνω από το hihi αληθή. Κάθε βήμα κοιτά το μέσο και πετά τη μισή περιοχή. Μετά από ⌈log⁡2(hi−lo+2)⌉\lceil \log_2(hi - lo + 2) \rceil βήματα μένει η απάντηση.

Στο Factory Machines το ok(t)\mathrm{ok}(t) είναι «σε χρόνο tt οι μηχανές φτιάχνουν τουλάχιστον kk προϊόντα», δηλαδή ∑i⌊t/ki⌋≥k\sum_i \lfloor t / k_i \rfloor \ge k. Αυτό είναι μονότονο ως προς tt και υπολογίζεται σε O(n)O(n).

Παγίδες

  • Το (lo + hi) / 2 υπερχειλίζει όταν τα όρια είναι κοντά στο 101810^{18}. Το lo + (hi - lo) / 2 όχι.
  • Το άνω όριο να είναι σίγουρα εφικτό. Στο Factory Machines είναι k⋅min⁡ikik \cdot \min_i k_i, δηλαδή έως 101810^{18}: χωράει σε long long, αλλά το άθροισμα μέσα στο ok\mathrm{ok} μπορεί να ξεπεράσει το όριο. Σταμάτα μόλις φτάσει το kk.
  • Γράψε το ok\mathrm{ok} πρώτα και δοκίμασέ το μόνο του σε δύο τιμές. Τα περισσότερα λάθη είναι εκεί, όχι στον βρόχο.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.

cpp/binary-search.cpp
// Binary search on a monotone predicate.
// ok(x) is false, false, ..., false, true, true, ... on [lo, hi].
// Returns the first x in [lo, hi] with ok(x) true, or hi + 1 if there is none.
// Invariant: everything below lo is false, everything above hi is true.

template <typename F>
ll firstTrue(ll lo, ll hi, F ok) {
    ll answer = hi + 1;
    while (lo <= hi) {
        ll mid = lo + (hi - lo) / 2;
        if (ok(mid)) {
            answer = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return answer;
}

Ελέγχθηκε σε 5.001 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Για εξάσκηση στο CSES

Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.

Περισσότερα στο USACO Guide

Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.