หากโจทย์ต้องการให้หาค่ามากสุดหรือน้อยสุดที่ทำให้เงื่อนไขหนึ่งเป็นจริง เทคนิคหนึ่งที่ควรนึกถึงคือการแปลงปัญหาเป็น Decision Problem แล้วทำการ Binary Search ทั้งนี้ จำเป็นต้องจัดเงื่อนไขให้มีคุณสมบัติ monotonicity ก่อน

สมมุติให้เรายอมให้สปอนเซอร์รับไก่ทอดไปกินได้ไม่เกินรายละ $a$ ชิ้น ถ้าเราสามารถทำได้ เราย่อมทำได้ในกรณีที่อนุญาตให้กินเกิน $a$ ชิ้นเช่นกัน แต่ถ้าทำไม่ได้ กรณีน้อยสุดที่ทำได้จำเป็นต้องอนุญาตให้กินมากกว่า $a$ ชิ้น

เราสามารถตรวจสอบว่าสามารถทำให้สปอนเซอร์รับไก่ทอดไปกินไม่เกินรายละ $a$ ชิ้นได้หรือไม่ โดยก่อนอื่นให้ preprocess ข้อมูลดังนี้ใน $O(N)$

• คำนวณว่าหากจะจัดไก่ทอดทางด้านซ้าย $i$ ชิ้นแรกให้สปอนเซอร์รายละไม่เกิน $a$ ชิ้น จำเป็นต้องให้สปอนเซอร์น้อยสุดกี่คน
  • สามารถใช้ greedy algorithm คำนวณได้โดยพยายามจัดไก่ทอดให้สปอนเซอร์รายเดียวให้ได้เรื่อย ๆ จนกว่าทำไม่ได้จึงเริ่มสปอนเซอร์รายใหม่
  • ให้จดคำตอบไว้ใน $L_i$
• คำนวณเช่นเดียวกันโดยเริ่มจากทางด้านขวา จดคำตอบให้ $R_i$ เท่ากับจำนวนสปอนเซอร์ที่น้อยที่สุดที่ทำได้หากจัดไก่ชิ้นที่ $i$ ถึง $N$ ให้ดีที่สุด

หลังจาก preprocess เสร็จแล้ว เราต้องตัดสินใจว่าจะเก็บไก่ทอดช่วงใดไว้กินเอง เพื่อลดจำนวนไก่ที่จำเป็นต้องนำไปจัดให้สปอนเซอร์ เราควรเลือกช่วงที่มีความยาวมากสุดที่เป็นไปได้ นั่นคือเลือกช่วงความยาว $M$ เสมอ

หากเลือกช่วง $[i,j]$ ส่วนที่เหลือจะจัดให้สปอนเซอร์ได้น้อยสุด $L_{i-1}+R_{j+1}$ ราย

• หากเกิน $K-1$ ราย แปลว่าเราจำเป็นต้องอนุญาตเกินรายละ $a$ ชิ้นเพื่อลดจำนวนสปอนเซอร์
• หากน้อยกว่า $K-1$ ราย เราสามารถจัดให้ครบ $K-1$ รายได้โดยใช้วิธีการแบ่งที่มีประสิทธิภาพน้อยกว่าที่คำนวณไว้ใน $L$ และ $R$ ดังนั้นคำตอบจะน้อยกว่าหรือเท่ากับค่า $a$ ที่ใช้ในกรณีนี้

ขั้นตอนนี้ใช้เวลา $O(N)$

เนื่องจากการ binary search ทำให้ต้องคำนวณตามวิธีที่กล่าวมาข้างต้นทั้งหมด $O(\log S)$ ครั้ง เมื่อ $S =$ ผลรวมของจำนวนไก่ทอดที่ติดกัน $M$ ส่วนที่มากที่สุด ($S \leq 10^9$ ในโจทย์) ดังนั้น Time Complexity รวมคือ $O(N \log S)$