On this page

ข้อ 54 · LC2300 Successful Pairs of Spells and Potions (คู่คาถากับยา) 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

sort (เรียง) potions แล้วสำหรับแต่ละ spell ใช้ bisect หา boundary (จุดเริ่ม) ของ potion ที่แรงพอ แล้ว count (นับ) ส่วนที่เหลือ

โจทย์ (LC2300): กำหนด array จำนวนเต็มบวกสองชุดคือ spells (ความแรงคาถา ยาว n) และ potions (ความแรงยา ยาว m) พร้อมจำนวนเต็ม success คู่ของคาถา i กับยา j จะสำเร็จ (successful) ก็ต่อเมื่อผลคูณ spells[i] * potions[j] มีค่ามากกว่าหรือเท่ากับ success ให้ return array pairs ความยาว n โดย pairs[i] คือจำนวนยาที่จับคู่กับคาถาตัวที่ i แล้วสำเร็จ

Example 1

Input:: spells = [5, 1, 3], potions = [1, 2, 3, 4, 5], success = 7
Output:: [4, 0, 3]
Explanation:: คาถา 5 คูณ [1,2,3,4,5] = [5,10,15,20,25] สำเร็จ 4 คู่ (ตั้งแต่ 10 ขึ้นไป) · คาถา 1 คูณได้ [1,2,3,4,5] ไม่ถึง 7 เลยสักคู่ · คาถา 3 คูณได้ [3,6,9,12,15] สำเร็จ 3 คู่

Example 2

Input:: spells = [3, 1, 2], potions = [8, 5, 8], success = 16
Output:: [2, 0, 2]
Explanation:: คาถา 3 คูณ [8,5,8] = [24,15,24] สำเร็จ 2 คู่ · คาถา 1 คูณได้ [8,5,8] ไม่ถึง 16 เลย · คาถา 2 คูณได้ [16,10,16] สำเร็จ 2 คู่

Constraints (ข้อจำกัด)

n == spells.length และ m == potions.length
1 <= n, m <= 10^5
1 <= spells[i], potions[i] <= 10^5
1 <= success <= 10^10

แนวทาง — ต้องใช้อะไร & คิดยังไง

โครงสร้างที่ใช้: sort (เรียง) + binary search (bisect) ถ้า sort potions ไว้ก่อน สำหรับ spell แต่ละตัว potion ที่แรงพอจะเป็น suffix (ท่อนหลัง) ที่ต่อเนื่องกันเสมอ (potion ยิ่งแรงยิ่งผ่าน) จึงหา boundary ของท่อนนั้นด้วย binary search แล้ว count จำนวนที่เหลือได้เลย

คิดแบบง่าย/ช้าก่อน: วิธี naive คือคูณ spell ทุกตัวกับ potion ทุกตัวเป็น O(n*m) ซึ่งช้าเมื่อทั้งสอง array ใหญ่ พอ sort potions แล้ว potion ที่ผ่าน threshold (เกณฑ์) จะเป็นช่วงต่อเนื่องด้านขวาสุดเสมอ เราจึงแค่หา boundary ของช่วงนั้น ลดเหลือ O((n+m) log m)

sort potions จากน้อยไปมาก
สำหรับ spell s แต่ละตัว: potion ที่ทำให้สำเร็จคือ potion >= success / s
compute threshold เป็น integer (จำนวนเต็ม) ปัดขึ้นด้วย need = (success + s - 1) // s เพื่อเลี่ยงปัญหา float
ใช้ bisect_left(potions, need) หา index แรกที่ potion >= need แล้ว count ที่ผ่าน = m - idx

จุดพลาดที่พบบ่อย

การหารด้วย float (ทศนิยม) success / s แล้วเจอ floating-point error (ความคลาดเคลื่อน) เลี่ยงด้วย integer ล้วน สูตร (success + s - 1) // s และถ้าไม่ sort potions ก่อนก็จะ binary search ไม่ได้เพราะช่วงจะไม่ sorted

ไล่ทีละสเต็ป

จำลอง spells = [5,1,3], potions sort แล้ว = [1,2,3,4,5], success = 7:

คาถา s	need = ceil(7/s)	idx (bisect_left)	m - idx
5	2	1	4
1	7	5	0
3	3	2	3

ผลลัพธ์ [4, 0, 3]

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

import bisect

def successful_pairs(spells, potions, success):
    potions.sort()                 # เรียงยาจากน้อยไปมาก
    m = len(potions)
    res = []
    for s in spells:
        # ต้องการ potion ที่ s * potion >= success  =>  potion >= success / s
        # หา index แรกที่ potion >= เกณฑ์ ด้วย binary search
        need = (success + s - 1) // s   # เพดานของ success / s (ปัดขึ้น)
        idx = bisect.bisect_left(potions, need)
        res.append(m - idx)             # จำนวน potion ตั้งแต่ idx จนจบ คือที่สำเร็จ
    return res

print(successful_pairs([5, 1, 3], [1, 2, 3, 4, 5], 7))  # [4, 0, 3]
print(successful_pairs([3, 1, 2], [8, 5, 8], 16))       # [2, 0, 2]

Output

[4, 0, 3]
[2, 0, 2]

หัวใจคือการมองว่า สำหรับ spell แรง s หนึ่งตัว potion ที่ทำให้สำเร็จคือ potion ที่มากกว่าหรือเท่ากับ success / s พอเรา sort potions แล้ว potion ที่ผ่าน threshold จะเป็นช่วงต่อเนื่องด้านขวาสุดเสมอ เราจึงแค่หา boundary ของช่วงนั้นด้วย bisect_left แล้ว count ที่ผ่านก็คือ ความยาวทั้งหมด ลบ index จุดเริ่ม

จุดพลาดที่พบบ่อยคือการหารด้วย float success / s แล้วเจอปัญหา floating-point error เราเลี่ยงด้วย integer ล้วน โดย compute ceiling (เพดาน ปัดขึ้น) ด้วยสูตร (success + s - 1) // s ซึ่งให้ค่าน้อยที่สุดของ potion ที่ยังทำให้ s * potion มากกว่าหรือเท่ากับ success พอดี ปลอดภัยกว่าใช้ float มาก

Time O((n + m) log m) sort potions เป็น O(m log m) แล้ว iterate spell n ตัว แต่ละตัว binary search เป็น O(log m) · Space O(1) นอกจาก array คำตอบ (sort potions in-place/ในที่เดิม)

💡 สรุป pattern

เมื่อต้อง count จำนวนที่ผ่าน threshold ใน array ให้ sort ก่อนแล้วช่วงที่ผ่านจะต่อเนื่อง ใช้ bisect หา boundary ของช่วงแทนการ count ทีละตัว และ compute threshold ปัดขึ้นด้วย integer เพื่อเลี่ยง float