คำอธิบายวิธีทำพร้อม code สำหรับข้อ toi11_labor

---

Author: Nagorn Phongphasura

---

Problem

---

สรุปโจทย์

มีกุลีทั้งหมด \(M\) คน โดยคนที่ \(i\) ใช้เวลา \(t_i\) ในการขนสินค้าชิ้นหนึ่ง ซึ่งเรามีสินค้าทั้งหมด \(N\) ชิ้น

---

สิ่งที่ต้องทำ

หาเวลาที่น้อยที่สุดที่ต้องใช้ในการขนสินค้าทั้ง \(N\) ชิ้น

---

ตัวอย่าง

พิจารณาภาพดังต่อไปนี้

---

Constraints

\(2 \leq M \leq 10^6\) (จำนวนกุลี)
\(1 \leq N \leq 10^{12}\) (จำนวนสินค้า)
\(1 \leq t_i \leq 10^4\) (เวลาที่กุลีคนที่ \(i\) ใช้ในการขนย้ายสินค้า \(1\) ชิ้น)

Prerequisites

• Binary Search

---

Solution

---

เทคนิคที่ใช้ในข้อนี้นะครับ ชื่อว่า Binary Search on Answer แต่ก่อนที่เราจะเรียนรู้ Binary Search on Answer เราจะต้องเรียน Binary Search กันก่อนครับ

Binary Search

ลองนึกเกมหนึ่งขึ้นมาดูนะครับ มีคนสองคน โดย:

1. คนแรกจะนึกตัวเลขขึ้นมาเลขหนึ่ง ตั้งแต่ \(1 - 100\)
2. คนที่สองจะต้องทายให้ถูก โดยเมื่อทายตัวเลข คนที่สองจะตอบแค่
   1. ตัวเลขที่นึกอยู่ มีค่ามากกว่า ตัวเลขที่ทาย
   2. ตัวเลขที่นึกอยู่ มีค่าน้อยกว่า ตัวเลขที่ทาย
   3. ตัวเลขที่นึกอยู่ มีค่าเท่ากับ ตัวเลขที่ทาย (ถือว่าจบเกม)

ทุกคนก็คงมีวิธีการทายเลข นั่นคือ การเลือกตัวเลขตรงกลาง แล้วแบ่งครึ่งไปเรื่อยๆ ตามคำตอบที่ได้รับมา จนกว่าจะทายถูก \((\text{เช่น } 50 \rightarrow 25 \rightarrow ... \text{หรือ } 50 \rightarrow 75 \rightarrow ...)\)

แต่รู้หรือไม่ว่า การ แบ่งครึ่งแบบนี้ คือ Algorithm ที่ชื่อว่า Binary Search

ซึ่ง Binary Search เนี่ย เนื่องจากเราจะ แบ่งครึ่ง เป็น 2 ส่วน ไปเรื่อยๆ เราจะได้ว่า Time Complexity: \(O(log\) \((r-l))\) เมื่อ \(l\) และ \(r\) คือเลขช่วงล่าง และเลขช่วงบน ตามลำดับ (ในกรณีนี้ \(l=1, r=100\))

Binary Search on Answer (พร้อมวิธีทำ)

เป็นเทคนิคการเขียนโปรแกรมที่ต่อยอดมาจาก Binary Search ซึ่งอาศัยหลักการว่า

"ถ้าหากว่าทำบางอย่าง ภายใต้ค่ากำหนด X ไม่ได้ ก็จะทำ ภายใต้ค่ากำหนดที่ (มากกว่า/น้อยกว่า) X ไม่ได้"

ในกรณีนี้ ข้อความดังกล่าว จะกลายเป็น

"หากยกของภายในเวลา X นาทีไม่ได้ จะไม่สามารถยกของภายในเวลาที่น้อยกว่า X นาทีได้"

โดยไอเดียในการทำ จะเป็น:

ขั้นตอน

1. กำหนดค่าน้อยสุด และค่ามากสุดที่เป็นไปได้ \((l, r)\) โดยในกรณีนี้ \(l = 1, r = 10^{18}\) (เนื่องจากจำนวนสินค้ามากสุด \(= 10^{12}\) และเวลาที่มากที่สุดที่กุลีคนหนึ่งจะใช้ขนของ \(= 10^6\) คูณกัน จะได้ \(10^{18}\) ซึ่งจริงๆแล้ว สามารถตั้งให้ \(r = \min(t_i) \times N\) เพื่อให้ช่วง Search แคบลง แต่จะใช้ \(10^{18}\) เพื่อความสะดวก)
2. หาค่ากลาง ระหว่าง \(l, r\) \((\)ตั้งชื่อว่า \(mid)\)
3. ตรวจสอบว่าสามารถทำภายใต้ค่ากลางได้มั้ย ในกรณีนี้คือ สามารถยกสินค้าทัน ภายในเวลา \(mid\) ได้มั้ย โดยการไล่กุลีทั้ง \(M\) คน จะได้ว่าจำนวนสินค้าที่หยิบได้สำหรับกุลีคนที่ \(i\) เท่ากับ \(\lfloor \frac{mid}{t_i} \rfloor\)
4. ตรวจสอบเงื่อนไข ในกรณีนี้คือ ถ้าผลรวมของสินค้าที่ยกทันใน \(mid\) นาที มีจำนวน \(\geq\) จำนวนสินค้าที่มี \((\sum_{i = 1}^{M} \lfloor \frac{mid}{t_i} \rfloor \geq N)\) จะถือว่ายกทัน
   1. ถ้าตรงเงื่อนไข ให้ลองปรับขอบเขต ในกรณีนี้ เราจะลดขอบบนลง \(: r = mid - 1\) (ลองลดขอบเขตเวลา แล้วตรวจสอบว่าทำได้มั้ย)
   2. ถ้าไม่ตรงเงื่อนไข ให้ลองปรับขอบเขต ในกรณีนี้ เราจะเพิ่มขอบล่างขึ้น \(: l = mid + 1\) (ลองเพิ่มขอบเขตเวลา แล้วตรวจสอบว่าทำได้มั้ย)
5. ทำซ้ำข้อ \(2-4\) จนกว่า \(l > r\) หรือก็คือ ทำระหว่างที่ \(l \leq r\) (นั่นคือ ค่ามันข้ามกันแล้ว ไม่จำเป็นต้องตรวจสอบแล้ว)

เนื่องจากการ Binary Search เราจะ Loop จำนวน \(log\) \(10^{18}\) รอบ ซึ่งในแต่ละครั้งที่เรา Loop เราจะไล่เช็กกุลีแต่ละคน รวมเป็นวนอีก \(N\) รอบ จะได้ว่าข้อนี้ จะ Loop จำนวน \(log\) \(10^{18}\) \(\times\) \(N\) รอบ เท่ากับ \(N\) \(log\) \(10^{18}\)

สามารถศึกษาเพิ่มเติมได้ที่นี่

---

วิธีทำ

เราสามารถใช้ Binary Search on Answer และไอเดียที่เขียนไว้ในนั้น (หากข้ามมา ก็กลับไปอ่านไอเดียตรงนั้นได้นะครับ) แล้ว Implement โค้ดตามตรงๆได้เลยครับ

---

Code

TOI11_Labor.cpp

#include <bits/stdc++.h>

using namespace std;

int main(){
    cin.tie(NULL)->sync_with_stdio(false);
    // input
    long long m, n;
    cin >> m >> n;
    vector<long long> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }
    // 1. กำหนดค่าน้อยสุด และค่ามากสุด (l, r)
    long long l = 1, r = 1e18; 
    long long ans = 1e18; // ตัวแปรเก็บคำตอบ
    while (l <= r) { // 5. ทำซ้ำเรื่อยๆ
        // 2. หาค่ากลาง ระหว่าง (l, r)
        long long mid = (l + r) / 2; 
        // 3. ไล่เก็บจำนวนสินค้าที่ยกได้
        long long sum = 0;
        for (int i = 0; i < m; i++) {
            sum += mid / a[i];
            if (sum >= n) break;
        }
        // 4. ตรวจสอบเงื่อนไข
        if (sum >= n) { // 4.1 ถ้ายกของทัน ก็ลองกดเวลาให้น้อยลง และบันทึกคำตอบ
            r = mid - 1;
            ans = min(mid, ans);
        }
        else { // 4.2 ถ้ายกของไม่ทัน ก็ลองเพิ่มเวลาให้มากขึ้น
            l = mid + 1;
        }
    } // 5. ทำซ้ำเรื่อยๆ
    // output
    cout << ans;
}

Total Time Complexity

\(O(N\) \(log\) \(10^{18})\)