19.3 binary search บนคำตอบ

โจทย์ค่าย 2 และ TOI จำนวนมากถามว่า "ค่าที่น้อยที่สุดที่ยังทำได้คือเท่าไร" หรือ "มากที่สุดที่ยังทำได้" เช่น เวลาน้อยสุดที่ทำงานเสร็จ ความยาวมากสุดที่ตัดได้ครบ หาคำตอบตรงๆ มักยากมาก แต่ถ้ามีคนเดาคำตอบมาให้หนึ่งค่า การตรวจว่าค่านั้นทำได้หรือไม่กลับง่าย หน้านี้ใช้ลูปจากหน้า 19.1 ค้นบน ช่วงของคำตอบ แทนช่วงของอาเรย์ เรียกกันว่า binary search on the answer

โจทย์แบ่งงาน

ร้านถ่ายเอกสารมีงานพิมพ์ต่อคิวอยู่ N งาน งานที่ i ยาว a_i แผ่น ร้านมีเครื่องพิมพ์ K เครื่อง ต้องแบ่งคิวเป็น K ช่วงที่ติดกันให้เครื่องละช่วง ห้ามสลับลำดับ และห้ามแบ่งงานเดียวไปสองเครื่อง ทุกเครื่องพิมพ์พร้อมกัน ร้านจึงเสร็จเมื่อเครื่องที่ได้งานมากที่สุดพิมพ์เสร็จ ต้องการแบ่งให้ จำนวนแผ่นของเครื่องที่หนักที่สุดน้อยที่สุด

เช่น งาน 30 10 50 20 40 10 30 กับเครื่อง 3 เครื่อง แบ่งเป็น 30 10 | 50 20 | 40 10 30 เครื่องที่หนักที่สุดพิมพ์ 80 แผ่น และแบ่งยังไงก็ไม่ได้ต่ำกว่า 80 ถ้าจะลองทุกวิธีแบ่ง ต้องเลือกจุดตัด K - 1 จุดจาก N - 1 ที่ N เป็นแสนมีวิธีแบ่งมากเกินนับ

กลับคำถาม

ถามกลับกันว่า ถ้ากำหนดให้แต่ละเครื่องพิมพ์ไม่เกิน X แผ่น ใช้เครื่องไม่เกิน K เครื่องได้ไหม คำถามนี้ตอบได้ในลูปเดียว ไล่งานตามคิว ใส่งานลงเครื่องปัจจุบันไปเรื่อยๆ จนกว่าใส่งานถัดไปแล้วจะเกิน X จึงเปิดเครื่องใหม่ เสร็จแล้วนับว่าใช้ไปกี่เครื่อง

ใส่ให้เต็มที่สุดก่อนเปิดเครื่องใหม่แบบนี้ใช้เครื่องน้อยที่สุดแล้ว เพราะวิธีแบ่งอื่นที่ให้เครื่องแรกรับงานน้อยกว่านี้ ก็มีแต่เหลืองานให้เครื่องถัดๆ ไปมากขึ้น ไม่มีทางทำให้ใช้เครื่องน้อยลง ลองกับงานชุดตัวอย่าง

คำตอบของโจทย์คือ X ที่น้อยที่สุดที่ตอบ "ใช่" ซึ่งคือรอยต่อแบบหน้า 19.1 พอดี ถ้ามั่นใจได้ว่าคำตอบเรียงเป็น "ไม่" ทั้งหมดแล้วค่อยเป็น "ใช่" ทั้งหมด

พิสูจน์ว่าเงื่อนไขเป็นทางเดียว

binary search ใช้ได้เมื่อคำตอบของคำถามใช่ไม่ใช่เปลี่ยนได้ครั้งเดียว ไม่สลับไปมา เรียกว่าเงื่อนไขเป็น ทางเดียว (monotonic) ต้องพิสูจน์ก่อนเขียนทุกครั้ง ข้อนี้พิสูจน์ได้สั้นมาก

ต่อมาหาช่วงที่คำตอบอยู่แน่นอน X ที่น้อยกว่างานที่ยาวที่สุดตอบ "ไม่" เสมอ เพราะงานนั้นใส่เครื่องไหนก็ไม่ได้ จึงเริ่ม lo ที่ค่ามากสุดของ a_i ส่วน X เท่ากับผลรวมทั้งหมดตอบ "ใช่" เสมอ เพราะเครื่องเดียวรับได้ทั้งคิว จึงเริ่ม hi ที่ผลรวม ทั้งหมดนี้รวมเป็นสามขั้นที่ต้องทำก่อนเขียนโจทย์แบบนี้ทุกข้อ

1. ตั้งคำถามใช่ไม่ใช่ ok(X) ที่ตรวจได้เร็ว มักเป็นลูปเดียวแบบ greedy คือไล่ทีละตัวแล้วเลือกทางที่ดีที่สุดตอนนั้นทันทีโดยไม่ย้อนกลับ วิธีคิดแบบนี้และการพิสูจน์ว่าถูกจะได้เรียนเต็มๆ ในบทที่ 23
2. พิสูจน์ว่าถ้า X ใช่ แล้ว X + 1 ใช่ด้วย (หรือกลับกัน ถ้า X ใช่ แล้ว X - 1 ใช่)
3. หา lo กับ hi ที่แน่ใจว่าคำตอบอยู่ระหว่างนั้น

#include <bits/stdc++.h>
using namespace std;

int machines_needed(const vector<int> &pages, long long limit)
{
    int machines = 1;
    long long load = 0;
    for (int i = 0; i < (int)pages.size(); i++) {
        if (load + pages[i] > limit) { // (1)!
            machines++;
            load = 0;
        }
        load += pages[i];
    }
    return machines;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> pages(n);
    long long lo = 0, hi = 0; // (2)!
    for (int i = 0; i < n; i++) {
        cin >> pages[i];
        lo = max(lo, (long long)pages[i]);
        hi += pages[i];
    }
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        int needed = machines_needed(pages, mid);
        cout << "lo=" << lo << " hi=" << hi << " mid=" << mid << " machines=" << needed << '\n';
        if (needed <= k) { // (3)!
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    cout << "answer = " << lo << '\n';
    return 0;
}

1. ใส่งานนี้แล้วเกิน จึงเปิดเครื่องใหม่ให้งานนี้ เครื่องใหม่รับงานนี้ได้แน่เพราะ limit ไม่เคยน้อยกว่างานที่ยาวที่สุด
2. ผลรวมของงานแสนงานงานละ 10⁹ แผ่นถึง 10¹⁴ จึงต้องเป็น long long ทั้ง lo hi และ mid
3. ถาม "ไม่เกิน K" ไม่ใช่ "เท่ากับ K" ถ้าใช้น้อยกว่า K เครื่อง ก็แบ่งช่วงที่มีหลายงานให้เครื่องที่ว่างได้ โดยไม่ทำให้เครื่องไหนหนักขึ้น

7 3
30 10 50 20 40 10 30

lo=50 hi=190 mid=120 machines=2
lo=50 hi=120 mid=85 machines=3
lo=50 hi=85 mid=67 machines=4
lo=68 hi=85 mid=76 machines=4
lo=77 hi=85 mid=81 machines=3
lo=77 hi=81 mid=79 machines=4
lo=80 hi=81 mid=80 machines=3
answer = 80

ลูปเหมือนหน้า 19.1 ทุกบรรทัด ต่างกันแค่ "ช่องที่ mid" ไม่ได้อ่านจากอาเรย์ แต่คำนวณจาก machines_needed ตรวจหนึ่งครั้งใช้ O(N) และช่วงตั้งแต่ lo ถึง hi กว้างไม่เกิน 10¹⁴ ซึ่งหารสองราว 47 ครั้งก็เหลือค่าเดียว ทั้งหมดจึงเป็น O(N log S) เมื่อ S คือผลรวม แสนงานตรวจราว 47 รอบ รวมไม่ถึงห้าล้านขั้น

มากที่สุดที่ยังทำได้

โรงเลื่อยมีต้นไม้เรียงกัน N ต้น ต้นที่ i สูง h_i เมตร เครื่องตัดตั้งใบเลื่อยไว้ที่ความสูง H แล้วเลื่อนผ่านทุกต้น ต้นที่สูงกว่า H จะถูกตัดส่วนที่เกิน H ออกมาเป็นไม้ ต้องการไม้รวมอย่างน้อย M เมตร และอยากตั้งใบเลื่อยให้ สูงที่สุด เพื่อไม่ตัดต้นไม้มากเกินจำเป็น โจทย์รับประกันว่าตั้งที่ความสูง 0 แล้วได้ไม้พอ

คำถามใช่ไม่ใช่คือ "ตั้งที่ H แล้วได้ไม้อย่างน้อย M ไหม" คราวนี้ทิศกลับกัน ถ้า H ทำได้ H - 1 ก็ทำได้ เพราะลดใบเลื่อยลง ทุกต้นให้ไม้เท่าเดิมหรือมากขึ้น ผลจึงเป็น "ใช่" ทั้งหมดทางซ้าย แล้ว "ไม่" ทั้งหมดทางขวา และคำตอบคือ "ใช่" ตัว สุดท้าย สลับบทบาทในลูปเป็น

• ถ้า mid ทำได้ คำตอบอยู่ที่ mid หรือสูงกว่า ตั้ง lo = mid
• ถ้าไม่ได้ คำตอบต่ำกว่า mid ตั้ง hi = mid - 1
• หาจุดกลางแบบ ปัดขึ้น lo + (hi - lo + 1) / 2 เหตุผลอยู่ในส่วนลองทำให้พัง

#include <bits/stdc++.h>
using namespace std;

long long wood_at(const vector<int> &heights, int blade)
{
    long long total = 0; // (1)!
    for (int i = 0; i < (int)heights.size(); i++) {
        if (heights[i] > blade) {
            total += heights[i] - blade;
        }
    }
    return total;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long need;
    cin >> n >> need;
    vector<int> heights(n);
    int lo = 0, hi = 0;
    for (int i = 0; i < n; i++) {
        cin >> heights[i];
        hi = max(hi, heights[i]);
    }
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2; // (2)!
        long long wood = wood_at(heights, mid);
        cout << "lo=" << lo << " hi=" << hi << " mid=" << mid << " wood=" << wood << '\n';
        if (wood >= need) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    cout << "blade height = " << lo << '\n';
    return 0;
}

1. ต้นไม้แสนต้นต้นละ 10⁹ เมตร ตัดที่ 0 ได้ไม้ถึง 10¹⁴ เมตร เกิน int
2. ปัดขึ้นเพื่อให้ mid มากกว่า lo เสมอ lo = mid จึงทำให้ช่วงสั้นลงจริง

5 20
18 25 12 30 21

lo=0 hi=30 mid=15 wood=34
lo=15 hi=30 mid=23 wood=9
lo=15 hi=22 mid=19 wood=19
lo=15 hi=18 mid=17 wood=26
lo=17 hi=18 mid=18 wood=22
blade height = 18

ตั้งที่ 18 ได้ 0 + 7 + 0 + 12 + 3 = 22 เมตร พอ แต่ตั้งที่ 19 ได้ 19 เมตร ไม่พอ คำตอบจึงเป็น 18 เริ่ม lo ที่ 0 เพราะโจทย์รับประกันว่าทำได้ และเริ่ม hi ที่ต้นที่สูงที่สุด เพราะตั้งสูงกว่านั้นไม่ได้ไม้เลย

ระยะห่างมากที่สุด

แนวที่สามที่เจอบ่อย ถนนเส้นหนึ่งมีจุดที่ตั้งเครื่องได้ N จุด ต้องตั้งเครื่อง C เครื่อง ให้ระยะห่างของคู่ที่อยู่ใกล้กันที่สุดมากที่สุด เช่น ตั้งเสาสัญญาณให้รบกวนกันน้อยที่สุด ทำตามสามขั้นเดิม

1. คำถามใช่ไม่ใช่ "ตั้ง C เครื่องให้ทุกคู่ห่างกันอย่างน้อย D ได้ไหม" ตอบด้วย greedy แบบที่บอกไว้ต้นหน้า เรียงตำแหน่ง ตั้งเครื่องแรกที่จุดซ้ายสุด แล้วไล่ไปทางขวา ตั้งเครื่องถัดไปที่จุดแรกที่ห่างจากเครื่องล่าสุดอย่างน้อย D นับว่าตั้งได้ถึง C เครื่องไหม
2. ถ้า D ทำได้ D - 1 ก็ทำได้ เพราะวิธีตั้งเดิมทุกคู่ห่างอย่างน้อย D ซึ่งมากกว่า D - 1 อยู่แล้ว ผลเป็น "ใช่" ทางซ้าย "ไม่" ทางขวา คำตอบคือ "ใช่" ตัวสุดท้าย ใช้แบบเดียวกับโจทย์ตัดไม้
3. D = 0 ทำได้เสมอ และ D ไม่มีทางเกินระยะจากจุดซ้ายสุดถึงขวาสุด

ข้อนี้ให้ลองเขียนเองในแบบฝึกหัด ทั้งสามโจทย์ในหน้านี้สรุปได้ตามตาราง

สังเกตคำในโจทย์ "ค่ามากที่สุดที่น้อยที่สุด" หรือ "ค่าน้อยที่สุดที่มากที่สุด" (minimize the maximum, maximize the minimum) เกือบทุกครั้งเป็นโจทย์แนวนี้

เร็วขึ้นแค่ไหน

วิธีตรงไปตรงมาของโจทย์แบ่งงานคือลอง X ทีละค่า เริ่มจากงานที่ยาวที่สุด เพิ่มทีละหนึ่งจนกว่า machines_needed จะได้ไม่เกิน K จำนวนรอบเท่ากับระยะจากงานที่ยาวที่สุดถึงคำตอบ ซึ่งอาจเป็นหลักแสน หลักล้าน หรือมากกว่านั้น วัดบนเครื่องเดียวกับหน้า 19.1 งานยาว 1 ถึง 1000 แผ่นแบบสุ่ม รันแต่ละแบบ 5 รอบ

ข้อมูลชุดแรก วิธีลองทีละค่าตรวจราวห้าหมื่นครั้ง แต่ binary search ตรวจแค่ 22 ครั้ง ชุดที่สองตรวจราวห้าหมื่นครั้งเหมือนเดิม แต่แต่ละครั้งไล่งานมากขึ้นสิบเท่า เวลาจึงโตตาม ถ้างานแต่ละงานยาวถึง 10⁹ แผ่น จำนวนค่าที่ต้องลองจะโตตามไปด้วย ส่วน binary search เพิ่มเป็นราว 47 ครั้งเท่านั้น

ลองทำให้พัง

แบบที่ 1 หาค่ามากสุดแต่ปัดจุดกลางลง

ในโปรแกรม cut-wood เปลี่ยนบรรทัดจุดกลางเป็น int mid = lo + (hi - lo) / 2; แบบหน้า 19.1 ป้อนข้อมูลเข้าเดิมที่ต้องการไม้ 20 เมตร ยังได้ blade height = 18 ถูกต้อง แต่เปลี่ยนเป็นต้องการไม้ 26 เมตร

lo=0 hi=30 mid=15 wood=34
lo=15 hi=30 mid=22 wood=11
lo=15 hi=21 mid=18 wood=22
lo=15 hi=17 mid=16 wood=30
lo=16 hi=17 mid=16 wood=30
lo=16 hi=17 mid=16 wood=30
lo=16 hi=17 mid=16 wood=30

ค้างที่ lo=16 hi=17 จุดกลางปัดลงได้ 16 ซึ่งทำได้ จึงตั้ง lo = 16 ค่าเดิม ช่วงไม่สั้นลง เป็นความผิดเดียวกับ lo = mid ในหน้า 19.1 แต่ซ่อนตัวกว่า เพราะบางข้อมูลเข้าผ่าน บางข้อมูลเข้าค้าง ขึ้นกับว่าช่วงจะเหลือสองค่าในจังหวะที่ lo ทำได้หรือไม่ กฎจำง่าย ฝั่งไหนเขียน = mid จุดกลางต้องปัดหนีฝั่งนั้น hi = mid ปัดลง lo = mid ปัดขึ้น

แบบที่ 2 เงื่อนไขไม่เป็นทางเดียว

อ่านโจทย์ว่า "แบ่งให้ K เครื่อง" แล้วเขียนเงื่อนไขเป็นใช้เครื่อง เท่ากับ K

#include <bits/stdc++.h>
using namespace std;

int machines_needed(const vector<int> &pages, long long limit)
{
    int machines = 1;
    long long load = 0;
    for (int i = 0; i < (int)pages.size(); i++) {
        if (load + pages[i] > limit) {
            machines++;
            load = 0;
        }
        load += pages[i];
    }
    return machines;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> pages(n);
    long long lo = 0, hi = 0;
    for (int i = 0; i < n; i++) {
        cin >> pages[i];
        lo = max(lo, (long long)pages[i]);
        hi += pages[i];
    }
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        int needed = machines_needed(pages, mid);
        cout << "lo=" << lo << " hi=" << hi << " mid=" << mid << " machines=" << needed << '\n';
        if (needed == k) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    cout << "answer = " << lo << '\n';
    return 0;
}

7 3
30 10 50 20 40 10 30

lo=50 hi=190 mid=120 machines=2
lo=121 hi=190 mid=155 machines=2
lo=156 hi=190 mid=173 machines=2
lo=174 hi=190 mid=182 machines=2
lo=183 hi=190 mid=186 machines=2
lo=187 hi=190 mid=188 machines=2
lo=189 hi=190 mid=189 machines=2
answer = 190

ได้ 190 แทนที่จะเป็น 80 เพราะ "ใช้เท่ากับ 3 เครื่อง" เป็นจริงแค่ตอน X อยู่ระหว่าง 80 ถึง 99 ต่ำกว่านั้นใช้ 4 ถึง 5 เครื่อง สูงกว่านั้นใช้ 1 ถึง 2 เครื่อง ผลจึงเป็น "ไม่ ... ใช่ ... ไม่" รอบแรกตรวจ 120 ได้ 2 เครื่อง โปรแกรมเข้าใจว่าคำตอบอยู่ทางขวาแล้วไม่กลับมาอีกเลย ก่อนเขียนต้องผ่านขั้นที่ 2 ให้ได้ ถ้าพิสูจน์ "X ใช่ แล้ว X + 1 ใช่" ไม่ได้ แปลว่าตั้งคำถามผิด

สรุป

• โจทย์ที่ถามค่าน้อยสุดหรือมากสุดที่ยังทำได้ ลองตั้งคำถามใช่ไม่ใช่ ok(X) แล้วค้นบนช่วงของคำตอบ
• ก่อนเขียนต้องพิสูจน์ว่าเงื่อนไขเป็นทางเดียว ถ้า X ใช่ แล้ว X + 1 ใช่ (หรือ X - 1 ใช่) และหา lo hi ที่คำตอบอยู่แน่
• หาใช่ตัวแรก hi = mid กับ lo = mid + 1 จุดกลางปัดลง หาใช่ตัวสุดท้าย lo = mid กับ hi = mid - 1 จุดกลางปัดขึ้น
• เวลาทั้งหมดคือเวลาตรวจหนึ่งครั้งคูณ log ของความกว้างช่วง เช่น O(N log S)
• ช่วงของคำตอบกับผลรวมในฟังก์ชันตรวจมักเกิน int ใช้ long long