การค้นหาแบบทวิภาคบนคำตอบ
เดาผลลัพธ์และตรวจสอบความเป็นไปได้
การค้นหาแบบทวิภาคบนคำตอบ เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
เดาแล้วตรวจสอบ
บางครั้งคุณคำนวณคำตอบโดยตรงไม่ได้ แต่สามารถ ตรวจสอบค่าที่เดาได้ การค้นหาคำตอบแบบไบนารีจะเปลี่ยนการหาค่าที่เหมาะที่สุดซึ่งยาก ให้กลายเป็นการตรวจสอบที่ง่าย
# guess X, ask: is X feasible?คุณสมบัติมหัศจรรย์
วิธีนี้ใช้ได้เมื่อความเป็นไปได้มีลักษณะ โมโนโทน กล่าวคือ หากค่าหนึ่งใช้ได้ ค่าที่มากกว่าทั้งหมดหรือค่าที่น้อยกว่าทั้งหมดก็ใช้ได้เช่นกัน ลำดับนั้นคือสิ่งที่คุณกำลังค้นหา
# feasible(X) true => feasible(X+1) trueกำหนดขอบเขตช่วงคำตอบ
ระบุคำตอบที่เป็นไปได้ค่าต่ำสุดและค่าสูงสุดเป็น low และ high สำหรับความจุขั้นต่ำ low คือขนาดของสิ่งของหนึ่งชิ้น และ high คือผลรวมทั้งหมด
low, high = max(weights), sum(weights)เขียนการตรวจสอบความเป็นไปได้
หัวใจของวิธีนี้คือ ฟังก์ชัน can(X) ที่คืนค่าเป็นจริงหากสามารถทำให้คำตอบ X เกิดขึ้นได้ โดยทั่วไปฟังก์ชันนี้ทำงานในเวลาเชิงเส้น
def can(cap):
# simulate and return True/False
...ตัวอย่าง: จัดส่งภายใน D วัน
เมื่อกำหนดความจุต่อวัน cap ให้เติมสิ่งของลงในแต่ละวันแบบโลภและนับจำนวนวัน can(cap) จะเป็นจริงเมื่อจำนวนวันไม่เกินขีดจำกัด D
def can(cap):
days, load = 1, 0
for w in weights:
if load + w > cap:
days += 1; load = 0
load += w
return days <= Dค้นหาความจุขั้นต่ำ
คุณต้องการค่า cap ที่น้อยที่สุดและผ่านการตรวจสอบ นี่คือการค้นหา ค่าจริงตัวแรกบนช่วงความจุ ดังนั้นให้นำแม่แบบ high = mid กลับมาใช้
while low < high:
mid = (low + high) // 2เก็บครึ่งที่เป็นไปได้ไว้
หาก can(mid) เป็นจริง ความจุที่น้อยกว่านี้อาจยังใช้ได้ จึงกำหนด high = mid มิฉะนั้นให้เพิ่มขอบเขตล่างด้วย low = mid + 1
if can(mid):
high = mid
else:
low = mid + 1คำนึงถึงงบเวลา
ค่าใช้จ่ายทั้งหมดคือ O(จำนวนครั้งตรวจสอบ x log ของช่วง) การตรวจสอบเชิงเส้นบนช่วงที่กว้างถึงหนึ่งพันล้านใช้การตรวจสอบเพียงประมาณ 30 ครั้ง จึงเร็วพอสำหรับขีดจำกัดที่เข้มงวด
# log2(1e9) is about 30 iterationsหาค่าสูงสุดแทนค่าต่ำสุด
หากต้องการหาค่าที่เป็นไปได้ซึ่ง มากที่สุด ให้กลับตรรกะเป็นการค้นหาค่าจริงตัวสุดท้าย เพิ่ม low เมื่อเป็นไปได้ และลด high เมื่อเป็นไปไม่ได้
if can(mid):
low = mid
else:
high = mid - 1คำตอบที่เป็นค่าจริง
สำหรับคำตอบแบบทศนิยม ให้ทำลูปตามจำนวนรอบคงที่ เช่น 100 รอบ แทนการใช้ mid แบบจำนวนเต็ม แต่ละรอบจะลดช่วงลงครึ่งหนึ่งและได้ ความแม่นยำสูงมากอย่างรวดเร็ว
for _ in range(100):
mid = (low + high) / 2มองหารูปแบบ
วลีอย่าง ค่าต่ำสุดของค่าสูงสุด ค่าสูงสุดของค่าต่ำสุด หรือ k ที่น้อยที่สุดซึ่งใช้ได้ ล้วนเป็น สัญญาณให้ค้นหาคำตอบแบบไบนารี ฝึกสังเกตวลีเหล่านี้
# 'minimize the maximum' => search answerตรวจสอบอย่างรวดเร็ว
ตัดสินใจว่าควรใช้การค้นหาคำตอบแบบไบนารีเมื่อใด
สรุปทบทวน: ค้นหาคำตอบ
ตอนนี้คุณสามารถกำหนดขอบเขตคำตอบ เขียน การตรวจสอบความเป็นไปได้ และค้นหาแบบไบนารีเพื่อหาค่าต่ำสุดหรือค่าสูงสุดได้แล้ว ปัญหายาก ๆ กลายเป็นการเดาแล้วตรวจสอบ 🏆
คำถามที่พบบ่อย
บทเรียน “การค้นหาแบบทวิภาคบนคำตอบ” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “การค้นหาแบบทวิภาคบนคำตอบ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “การค้นหาแบบทวิภาคบนคำตอบ”
เดาผลลัพธ์และตรวจสอบความเป็นไปได้ คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “การค้นหาแบบทวิภาคบนคำตอบ” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การค้นหาแบบทวิภาคคลาสสิกที่ไร้บั๊ก
- bisect_left และ bisect_right
- True แรก: การค้นหาแบบทวิภาคด้วยภาคแสดง
- การค้นหาแบบทวิภาคบนคำตอบ