23.4 greedy กับ priority_queue

greedy ในหน้าก่อนๆ เรียงข้อมูลครั้งเดียวแล้วไล่ไปตามลำดับ แต่บางโจทย์ "ตัวที่ดีที่สุดตอนนี้" เปลี่ยนไปทุกครั้งที่เลือก เพราะการเลือกแต่ละครั้งสร้างของชิ้นใหม่ขึ้นมา หรือทำให้ต้องคืนของที่เคยเลือกไว้ การเรียงครั้งเดียวจึงไม่พอ ต้องใช้ priority_queue จากหน้า 20.5 ที่หยิบตัวน้อยสุดหรือมากสุดได้ใน O(log N) ทุกครั้ง หน้านี้มีสองโจทย์ คือรวมเชือกให้ต้นทุนน้อยที่สุด และเลือกงานให้ได้ค่าจ้างมากที่สุดก่อนเส้นตาย

รวมเชือกให้ต้นทุนน้อยที่สุด

ร้านอุปกรณ์เดินป่ามีเชือก N เส้น ยาวไม่เท่ากัน ต้องต่อทั้งหมดให้เป็นเส้นเดียว ต่อได้ทีละสองเส้น ค่าต่อแต่ละครั้งเท่ากับความยาวรวมของสองเส้นที่ต่อ (เส้นยาวใช้เวลาเตรียมนาน) เส้นที่ต่อแล้วเอาไปต่อกับเส้นอื่นได้อีก ต้องการให้ ค่าต่อรวมน้อยที่สุด

เชือกเส้นที่ถูกต่อเร็ว จะถูกนับความยาวซ้ำในทุกการต่อหลังจากนั้น เหมือนคนหน้าคิวในหน้า 23.3 เส้นสั้นจึงควรถูกต่อก่อน กฎ greedy คือ ต่อสองเส้นที่สั้นที่สุดที่มีอยู่ตอนนี้ เส้นใหม่ที่ได้กลับเข้ากอง แล้วทำซ้ำ เส้นใหม่อาจไม่ใช่เส้นที่สั้นที่สุดในรอบถัดไป ต้องหาสองเส้นที่สั้นที่สุดใหม่ทุกรอบ ซึ่งเป็นงานของ priority_queue แบบน้อยสุดก่อน

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

int main()
{
    int n;
    cin >> n;
    priority_queue<long long, vector<long long>, greater<long long>> ropes; // (1)!
    for (int i = 0; i < n; i++) {
        long long length;
        cin >> length;
        ropes.push(length);
    }
    long long cost = 0;
    while (ropes.size() > 1) {
        long long a = ropes.top();
        ropes.pop();
        long long b = ropes.top();
        ropes.pop();
        cout << "join " << a << " + " << b << " = " << a + b << '\n';
        cost += a + b;
        ropes.push(a + b); // (2)!
    }
    cout << "total cost = " << cost << '\n';
    return 0;
}

1. heap แบบน้อยสุดก่อนด้วย greater ตามหน้า 20.5 ความยาวรวมโตได้ถึงผลรวมของทุกเส้น และค่าต่อรวมยังมากกว่านั้นอีกหลายเท่า จึงใช้ long long ทั้งหมด
2. เส้นที่ต่อแล้วกลับเข้ากอง จะถูกหยิบมาต่ออีกเมื่อมันอยู่ในสองเส้นที่สั้นที่สุด

5
30 20 50 40 60

join 20 + 30 = 50
join 40 + 50 = 90
join 50 + 60 = 110
join 90 + 110 = 200
total cost = 450

รอบที่สอง เส้น 50 ที่เพิ่งต่อได้ยาวเท่ากับเส้น 50 เดิม heap หยิบเส้นไหนก่อนก็ได้ค่าเท่ากัน รอบที่สามไม่ได้ต่อเส้น 90 ที่เพิ่งได้ เพราะ 50 กับ 60 สั้นกว่า มี N - 1 รอบ รอบละ push pop ไม่กี่ครั้ง รวมเป็น O(N log N)

ทำไมต้องสองเส้นที่สั้นที่สุด

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

ค่าต่อรวมคือผลรวมของความยาวคูณจำนวนครั้งที่ถูกนับ ถ้ามีวิธีไหนที่เส้นยาวถูกนับมากครั้งกว่าเส้นสั้น สลับตำแหน่งสองเส้นนั้นในแผนการต่อ ค่ารวมจะไม่เพิ่ม ต่อไปดูเส้น X ที่ถูกนับมากครั้งที่สุด ตอนที่ X ถูกต่อครั้งแรก มันต่อกับเส้น Y และนับจากนั้นทั้งคู่ถูกนับเพิ่มเท่ากันทุกครั้ง ถ้า Y เป็นเส้นที่ต่อมาแล้ว เชือกเดิมที่อยู่ข้างใน Y จะถูกนับมากกว่า X อย่างน้อยหนึ่งครั้ง ขัดกับที่ X ถูกนับมากที่สุด Y จึงเป็นเชือกเดิมที่ถูกนับเท่ากับ X พอดี สองเส้นที่ถูกนับมากที่สุดจึงถูกต่อกันเองเสมอ สลับให้สองตำแหน่งนี้เป็นสองเส้นที่สั้นที่สุด ค่ารวมไม่เพิ่มตามเหตุผลข้างบน แล้วย้ายการต่อคู่นี้ไปทำเป็นครั้งแรก ซึ่งไม่ทำให้เส้นไหนถูกนับมากหรือน้อยลง ในวิธีที่ดีที่สุดจึงมีแบบหนึ่งที่สองเส้นที่สั้นที่สุดถูกต่อเข้าด้วยกันเป็นครั้งแรก ซึ่งก็คือสิ่งที่ greedy ทำ หลังจากนั้นเส้นที่ต่อแล้วก็เป็นเชือกเส้นหนึ่งในโจทย์ที่เล็กลง ใช้เหตุผลเดิมซ้ำ ความคิดเดียวกันนี้ใช้สร้าง Huffman code ซึ่งให้ตัวอักษรที่เจอบ่อยมีรหัสสั้น เป็นหลักการของการบีบอัดไฟล์

เลือกงานให้ได้ค่าจ้างมากที่สุดก่อนเส้นตาย

ร้านซ่อมคอมพิวเตอร์มีช่างคนเดียว มีงานเสนอเข้ามา N งาน ทุกงานใช้เวลาหนึ่งวันเต็ม งานที่ i ต้องเสร็จภายในวันที่ d_i และได้ค่าจ้าง p_i บาท งานที่ทำไม่ทันไม่ต้องรับ อยากเลือกงานให้ได้ ค่าจ้างรวมมากที่สุด

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

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

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> jobs(n);
    int last_day = 0;
    for (int i = 0; i < n; i++) {
        int deadline, pay;
        cin >> deadline >> pay;
        jobs[i] = {pay, deadline};
        last_day = max(last_day, deadline);
    }
    sort(jobs.rbegin(), jobs.rend()); // (1)!
    vector<bool> busy(last_day + 1, false); // (2)!
    long long total = 0;
    for (int i = 0; i < n; i++) {
        int pay = jobs[i].first;
        int deadline = jobs[i].second;
        for (int day = deadline; day >= 1; day--) { // (3)!
            if (!busy[day]) {
                busy[day] = true;
                total += pay;
                cout << "pay " << pay << " on day " << day << '\n';
                break;
            }
        }
    }
    cout << "total = " << total << '\n';
    return 0;
}

1. เก็บเป็น {pay, deadline} แล้วเรียงจากท้ายไปหน้าตามหน้า 16.3 ได้ค่าจ้างจากมากไปน้อย
2. vector<bool> คือ vector ที่แต่ละช่องเก็บ bool จากหน้า 15.5 ใช้แบบเดียวกับ vector ชนิดอื่น ช่อง busy[day] จำว่าวันนั้นมีงานลงแล้วหรือยัง เรื่องความเร็วของมันมีข้อควรระวัง ดูในส่วนวัดเวลาข้างล่าง
3. ไล่จากวันเส้นตายถอยลงมาหาวันว่างวันแรกที่เจอ ซึ่งก็คือวันว่างวันสุดท้ายที่ยังทันเส้นตาย

6
1 30
1 20
2 40
2 35
3 25
3 50

pay 50 on day 3
pay 40 on day 2
pay 35 on day 1
total = 125

ข้อมูลเข้าแต่ละบรรทัดคือเส้นตายกับค่าจ้าง งาน 50 บาทลงวันที่ 3 งาน 40 บาทลงวันที่ 2 งาน 35 บาทเส้นตายวันที่ 2 แต่วันที่ 2 ไม่ว่างแล้ว จึงถอยไปวันที่ 1 ที่เหลือไม่มีวันว่างให้ลง ได้ 125 บาท ถูกต้อง แต่ช้า ถ้ามีหลายงานที่เส้นตายเดียวกันมากๆ งานหลังๆ ต้องไล่ข้ามวันที่ไม่ว่างนับแสนวันก่อนจะเจอวันว่าง เป็น O(N × D) เมื่อ D คือเส้นตายที่มากที่สุด หน้า 23.5 จะแสดงว่าทำไมต้องเป็นวันว่างวันสุดท้าย ไม่ใช่วันแรก

เก็บงานที่ดีที่สุดไว้ใน heap

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

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

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> jobs(n);
    for (int i = 0; i < n; i++) {
        cin >> jobs[i].first >> jobs[i].second;
    }
    sort(jobs.begin(), jobs.end()); // (1)!
    priority_queue<int, vector<int>, greater<int>> kept;
    long long total = 0;
    for (int i = 0; i < n; i++) {
        int deadline = jobs[i].first;
        int pay = jobs[i].second;
        kept.push(pay);
        total += pay;
        if ((int)kept.size() > deadline) { // (2)!
            cout << "deadline " << deadline << ": drop " << kept.top() << '\n';
            total -= kept.top();
            kept.pop();
        }
    }
    cout << "total = " << total << '\n';
    return 0;
}

1. pair เป็น {deadline, pay} จึงเรียงตามเส้นตายจากเร็วไปช้า
2. งานที่รับไว้มีมากกว่าจำนวนวันจนถึงเส้นตายนี้ ทำไม่ทันแน่ คืนงานที่ค่าจ้างน้อยที่สุดหนึ่งงาน เพิ่มทีละงานจึงเกินได้ทีละหนึ่ง คืนหนึ่งงานก็พอ

6
1 30
1 20
2 40
2 35
3 25
3 50

deadline 1: drop 20
deadline 2: drop 30
deadline 3: drop 25
total = 125

ถึงเส้นตายวันที่ 1 รับงาน 20 กับ 30 ไว้ เกินหนึ่งวัน คืนงาน 20 ถึงวันที่ 2 รับ 35 กับ 40 เพิ่ม มีสามงานในสองวัน คืนงาน 30 ทั้งที่มันเคยถูกรับไว้แล้ว นี่คือจุดที่ greedy แบบเรียงครั้งเดียวทำไม่ได้ ถึงวันที่ 3 คืนงาน 25 เหลือ 35 40 50 รวม 125 บาท เท่ากับวิธีก่อน

งานที่เหลือในกองทำทันหมดแน่นอน เพราะถ้าเอามาเรียงตามเส้นตายแล้วทำวันละงาน งานลำดับที่ k ทำในวันที่ k และตอนที่มันถูกรับเข้ากอง กองมีงานไม่เกินเส้นตายของมัน จึงได้ k ไม่เกินเส้นตาย ส่วนงานที่ถูกคืน คืองานที่ถูกที่สุดในบรรดางานที่แย่งวันชุดเดียวกัน คืนงานอื่นแทนก็ได้เงินไม่มากกว่านี้ ทุกงานเข้าและออกจาก heap ไม่เกินอย่างละครั้ง รวมกับการเรียงเป็น O(N log N) และเส้นตายจะใหญ่ถึง 10⁹ ก็ได้ เพราะไม่ต้องมีอาเรย์ของวัน

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

วัดบนเครื่องเดียวกับหน้า 23.1 รันแต่ละแบบ 5 รอบ วัดทั้งโปรแกรมรวมการอ่านข้อมูล ทุกโปรแกรมตัดบรรทัดที่พิมพ์ระหว่างทางออกและเปิดการอ่านเขียนแบบเร็ว การรวมเชือกแบบตรงไปตรงมาคือเก็บเชือกใน vector แล้วไล่หาสองเส้นที่สั้นที่สุดใหม่ทุกรอบ เป็น O(N²) เชือกยาวสุ่ม 1 ถึง 10⁶

งานซ่อมคอมพิวเตอร์ เส้นตายสุ่มระหว่าง N/2 ถึง N งานจำนวนมากจึงแย่งวันท้ายๆ กัน ค่าจ้างสุ่ม 1 ถึง 10⁶

วิธีวันว่างวันสุดท้ายแบบ Code::Blocks ช้ากว่าแบบ -O2 เกือบ 60 เท่า ส่วนใหญ่มาจาก vector<bool> ซึ่งเก็บข้อมูลเป็นบิต ทุกครั้งที่อ่านต้องแกะบิตออกมา ถ้าไม่มี -O2 งานนี้ช้ามาก ลองเปลี่ยนเป็น vector<char> แล้ววัดที่ N หนึ่งแสน 5 รอบ แบบ Code::Blocks เหลือ 3.9 วินาที แบบ -O2 เหลือ 0.63 วินาที แต่ไม่ว่าจะแก้แบบไหน ที่ N สองแสนก็ยังเกินหนึ่งวินาที (vector<char> แบบ -O2 ได้ 2.5 วินาที) ส่วน heap เร็วเท่าการอ่านข้อมูลทั้งสองโจทย์

ลองทำให้พัง

แบบที่ 1 เรียงครั้งเดียวแล้วต่อเรียงแถว

คิดว่าเส้นสั้นต้องต่อก่อน จึงเรียงครั้งเดียวแล้วต่อจากสั้นไปยาว

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

int main()
{
    int n;
    cin >> n;
    vector<long long> ropes(n);
    for (int i = 0; i < n; i++) {
        cin >> ropes[i];
    }
    sort(ropes.begin(), ropes.end());
    long long current = ropes[0], cost = 0;
    for (int i = 1; i < n; i++) {
        cout << "join " << current << " + " << ropes[i] << " = " << current + ropes[i] << '\n';
        current += ropes[i];
        cost += current;
    }
    cout << "total cost = " << cost << '\n';
    return 0;
}

5
30 20 50 40 60

join 20 + 30 = 50
join 50 + 40 = 90
join 90 + 50 = 140
join 140 + 60 = 200
total cost = 480

ได้ 480 แทน 450 บรรทัดที่สามต่อเส้น 90 เข้ากับ 50 ทั้งที่ตอนนั้นมีเส้น 50 กับ 60 ซึ่งต่อกันได้ถูกกว่า เส้นที่ต่อแล้วยาวขึ้นเรื่อยๆ และถูกนับซ้ำทุกครั้ง ตัวอย่างที่มีเชือกแค่สามเส้นจะได้คำตอบเท่ากันทั้งสองวิธี เพราะแบบไหนก็ต้องต่อสองเส้นที่สั้นที่สุดก่อน ข้อผิดนี้จึงหลุดตัวอย่างในโจทย์ได้ง่าย

แบบที่ 2 ลืม greater

ในโปรแกรม keep-best ประกาศ heap เป็น priority_queue<int> kept; เฉยๆ

deadline 1: drop 30
deadline 2: drop 40
deadline 3: drop 50
total = 80

heap ปกติให้ค่ามากสุดก่อน ทุกครั้งที่รับงานเกิน จึงคืนงานที่ค่าจ้าง มากที่สุด ได้ 80 แทน 125 ข้อนี้คอมไพล์ผ่านและรันได้ปกติ ทางเดียวที่จะจับได้คือทดสอบกับตัวอย่างที่คำนวณด้วยมือไว้แล้ว ทุกครั้งที่ประกาศ priority_queue ให้ถามตัวเองว่าต้องการหยิบตัวมากหรือตัวน้อยออกก่อน

สรุป

• ใช้ priority_queue เมื่อตัวที่ดีที่สุดเปลี่ยนไปหลังการเลือกแต่ละครั้ง เช่นมีของใหม่เกิดขึ้น หรือต้องคืนของที่เคยเลือก
• รวมเชือกให้ต้นทุนน้อยสุด ต่อสองเส้นที่สั้นที่สุดทุกรอบ แล้วใส่เส้นใหม่กลับเข้า heap ได้ O(N log N)
• เลือกงานวันละงานก่อนเส้นตาย ไล่ตามเส้นตาย รับทุกงานเข้า heap แบบน้อยสุดก่อน รับเกินจำนวนวันเมื่อไรให้คืนงานค่าจ้างน้อยสุด
• เรียงครั้งเดียวแล้วต่อเรียงแถวผิด และ heap ผิดทิศก็ผิดโดยไม่มีอะไรเตือน