ในข้อนี้เราต้องการหาเวลาที่น้อยที่สุดกุลีที่สามารถขนถ่ายสินค้าได้ครบ

หากเราพิจารณาค่า $T$ ใด ๆ โดยนิยามให้ $F(T)$ หมายถึงฟังก์ชันแทนจำนวนสินค้าที่มากที่สุดที่กุลีทั้งหมดสามารถขนถ่ายได้โดยใช้เวลาไม่เกิน $T$ จะสังเกตว่า $F(T) \leq F(T+1)$ เสมอ เพราะถ้ากุลีคนที่ $i$ ใด ๆ ขนสินค้าได้ $K$ ชิ้นในเวลาไม่เกิน $T$ หน่วยก็แปลว่าย่อมสามารถขนได้ด้วยเวลา $T+1$ หน่วยเช่นกันเพราะ $T+1 > T \geq t_i*K$ จากเหตุผลดังกล่าวจะได้ว่าฟังก์ชัน $F(T)$ เป็นฟังก์ชัน Monotone ดังนั้นการหาค่า $T$ ที่น้อยที่สุดที่ $F(T) \geq N$ สามารถหาได้ด้วยการ Binary Search ค่า $T$ โดยตรง

การทำ Binary Search บนช่วงคำตอบนั้นเริ่มได้จากการกำหนดตัวแปร $l$ และ $r$ แทนจุดเริ่มต้นและจุดสิ้นสุดของช่วงโดยในตอนเริ่มต้นกำหนดให้ $l=1$ และ $r=\min \limits_{1 \leq i \leq M} \{ t_i \} \cdot N$ ระหว่างการทำ Binary Search หากกำลังพิจารณาคำตอบในช่วง $[l,r]$ อยู่โดย mid = (l+r)/2 จะมีกรณีที่ต้องพิจารณาเพื่อเปลี่ยนช่วงคำตอบ 2 กรณีดังนี้

• $F(mid) \geq N$ นั่นหมายความว่าคำตอบที่ต้องการนั้นมีค่าน้อยกว่าหรือเท่ากับ mid แน่นอน จึงเปลี่ยนช่วงไปพิจารณาช่วง $[l,mid]$ ต่อไป
• $F(mid) < N$ นั่นหมายความว่าคำตอบที่ต้องการนั้นมากกว่า mid แน่นอน จึงเปลี่ยนช่วงไปพิจารณาช่วง $[mid+1,r]$ ต่อไป

วิธีในการคำนวณค่า $F(T)$ สำหรับค่า $T$ ใด ๆ นั้นสามารถทำได้โดยการไล่คิดผลรวมจำนวนสินค้าที่มากที่สุดที่กุลีสามารถขนถ่ายได้โดยใช้เวลาไม่เกิน $T$ ตั้งแต่กุลีคนที่ $1,2,3,...,M$ กล่าวคือ $F(T) = \sum \limits_{i=1}^{M} \left \lfloor{\frac{T}{t_i}}\right \rfloor$

วิธีการดังกล่าวจะใช้ Time Complexity $\mathcal{O}(M)$ ต่อการคิด $F(T)$ 1 ครั้ง เพราะได้ไล่คิดในทุกๆ index $i$ ตั้งแต่ $i = 1,2,3,...,M$ ซึ่งถ้าคิดในกรณี Worst Case Time Complexity จะคิด $F(T)$ $\log (N \cdot maxt)$ ครั้งเมื่อ $maxt =$ ค่า $t_i$ มากสุดที่เป็นไปได้ใน input = $10^6$ ดังนั้นจะมี Worst Case Time Complexity รวม $\mathcal{O}(M\log (N \cdot maxt))$ เมื่อ $maxt =$ ค่า $t_i$ มากสุดที่เป็นไปได้ใน input = $10^6$

โค้ดตัวอย่างดังนี้

#include <bits/stdc++.h>

using namespace std;
long long n, m;
long long pw[1000100];
int main() {
  scanf("%lld %lld", &m, &n);
  for (int i = 1; i <= m; i++) {
    scanf("%lld", &pw[i]);
  }
  long long l = 1, r = 1000000LL * n;
  while (l < r) {
    long long mid = (l + r) / 2;
    long long all = 0;
    for (int i = 1; i <= m; i++) {
      all += mid / pw[i];
    }
    if (all >= n)
      r = mid;
    else
      l = mid + 1;
  }
  printf("%lld", l);
  return 0;