โจทย์ข้อ Slay the Dragon จาก Codeforces

โจทย์

ความยาก ★★☆☆☆

มีคนทั้งหมด $n$ คน แต่ละคนมีพลัง $a_i$ มีมังกรทั้งหมด $m$ ตัว แต่ละตัวมีพลังป้องกัน $x_i$ และพลังโจมตี $y_i$

การที่จะต่อสู้กับมังกรตัวที่ $i$ ชนะนั้น เราต้องเลือกคนนึงที่มีพลังอย่างน้อย $x_i$ ไปโจมตีมังกร และคนที่เหลือต้องมีพลังรวมอย่างน้อย $y_i$ เพื่อป้องกันมังกร

เราสามารถเพิ่มพลังให้คนที่ $i$ ได้โดยการใช้เหรียญกับคนนั้น ซึ่ง 1 เหรียญจะเพิ่มพลังของคนที่เลือกได้ 1 หน่วย ถามว่าสำหรับการจะออกไปสู้มังกรแต่ละตัวนั้นจะต้องใช้เหรียญอย่างน้อยกี่เหรียญเพื่อชนะมังกรตัวนั้น

---

ข้อมูลนำเข้า

บรรทัดแรก ระบุ $n$ แทนจำนวนคน ($2 ≤ n ≤ 200\,000$)
บรรทัดต่อมา ระบุจำนวนเต็ม $n$ จำนวน แทนพลัง ($a_i$) ของคนที่ $i$ ($1 \leq a_i \leq 10^{12}$)
บรรทัดต่อมา ระบุจำนวนเต็ม $m$ แทนจำนวนคำถาม ($1 ≤ m ≤ 200\,000$)

$m$ บรรทัดต่อมา ระบุ $x_i, y_i$ แทนพลังป้องกันและพลังโจมตีของมังกรตัวที่ $i$ ($1 ≤ x_i ≤ 10^{12},1 ≤ y_i ≤ 10^{18}$)

ข้อมูลส่งออก

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

ตัวอย่างข้อมูลนำเข้าและข้อมูลส่งออก

คำอธิบายตัวอย่างแรก:

การที่จะสู้มังกรตัวที่ 1 ชนะนั้น เราจะเพิ่มพลังของคนที่ 3 และนำคนนั้นไปโจมตีมังกร ทำให้พลังป้องกันเป็น 12 พลังโจมตี 3 ซึ่งใช้เหรียญแค่ 1 เหรียญ

การที่จะสู้มังกรตัวที่ 2 ชนะนั้น เราจะเพิ่มพลังของคนที่ 2 และ 3 และนำคนที่ 2 ไปโจมตีมังกร ทำให้พลังป้องกันคือ 9 พลังโจมตี 7 และใช้เหรียญ 2 เหรียญ

---

วิเคราะห์โจทย์

ข้อสังเกต

ถ้าต้องไปสู้มังกรที่มีค่าพลังป้องกันเป็น x จะส่งคนที่มีพลัง x หรือ x+1 หรือมากกว่า ก็ไม่ได้มีอะไรต่างกัน เพราะก็ล้มมังกรได้อยู่ดี

แต่นั่นก็ไม่ได้แปลว่าเราจำเป็นต้องส่งคนที่สู้ได้เลยเสมอไป จะส่งคนที่ต้องไปเพิ่มพลังก่อนก็ได้ แล้วถ้าเป็นกรณีนี้จะส่งใครดีล่ะ?

หรือส่งคนอื่นดี?

ถ้าสมมติว่าเราจะเลือกคนที่ $c$ ที่มีพลัง $a_c$ แล้วพลังไม่พอไปสู้กับมังกรที่มีพลัง $x$ แปลว่าเราต้องเพิ่มพลังอีก $x - a_c$ หน่วยเพื่อที่จะทำให้มันพอ

ส่วนในด้านของการป้องกันเราจะเหลือพลังอีก $\sum^{n}_{i}a_i - a_c$ หน่วย (คนที่เหลือทั้งหมดรวมกัน) ที่ต้องใช้ในการป้องกันการโจมตี ซึ่งถ้าพลังป้องกันไม่พอก็ต้องเพิ่มพลังอีก $y - (\sum_{i}^{n}a_i -a_c)$ หน่วย

ซึ่งแปลว่าเราต้องเพิ่มพลังให้รวมทั้งหมด

โดยที่เราจะต้องใส่ค่า max ลงไปเพราะถ้ามันเยอะกว่าพลังโจมตีของมังกรอยู่แล้ว ก็ไม่ต้องเพิ่มพลัง (เราไม่สามารถลดพลังได้อ่ะนะ 🤣)

จะเห็นได้ว่าส่งคนที่มีพลังเยอะสุดดีกว่า (ที่ต้องเพิ่มพลังน้อยสุดหน่ะนะ) เพราะถึงปล่อยให้พลังป้องกันเยอะขึ้น มันก็ไม่ได้ทำให้ค่า cost ในการเพิ่มพลังน้อยลงเลย จริงๆบางทีจะทำให้มันแย่ลงด้วยซ้ำเพราะ ในส่วนของการป้องกัน มันขอแค่ให้พอดีก็พอแล้ว

แล้วทีนี้เลือกส่งใครดี

ทั้งสองกรณีก็เข้าท่าทั้งคู่แหละ จะส่งคนที่พลังมากกว่า(ที่น้อยที่สุด)เลยก็ได้ หรือจะส่งคนที่ต้องเพิ่มพลังนิดหน่อยก็ได้ ดังนั้นก็ไม่ต้องคิดมาก… ตรวจสอบมันทั้งคู่เลยนั่นแหละ มันมีแค่สองคนเอง 😆

หาคำตอบ

ทีนี้ก็จะเหลืออยู่ปัญหาเดียวละ… จะหาคนให้เร็วพอได้ยังไง เพราะว่าโจทย์นี้มันถามหลายรอบอยู่เหมือนกัน จะให้มา for loop ทุกรอบก็คงจะไม่ดีอ่ะนะ

ซึ่งเราก็แก้ได้ไม่ยากด้วยการ sort พลังของทุกคนก่อน แล้วทำ binary search ค่าพลังพวกนั้นก็ได้ละ แถมได้ประโยชน์เพิ่มด้วยว่าค่าทั้งสองคนที่ต้องเอาไปคิดมันอยู่ติดกันเลย

ลิงก์

ลิงก์โจทย์ slay the dragon

https://codeforces.com/problemset/problem/1574/C

Extra Challenge

1. ถ้าลดจำนวนคำถามเหลือไม่เกิน 1,000 คำถาม จำนวนคนเหลือไม่เกิน 10,000 คน และสามารถส่งคนไปสู้มังกรได้อย่างมาก 2 คน เราต้องคิดแตกต่างจากเดิมอย่างไรบ้าง
2. ถ้าแต่ละคนมีพลังแยกเป็น 2 ประเภทคือพลังป้องกันและพลังโจมตี และการใช้เหรียญ 1 ประเภทสามารถเพิ่มพลังป้องกันหรือพลังโจมตีได้เพียงค่าเดียวเท่านั้น ถามว่าสำหรับมังกรแต่ละตัวนั้น คิดแตกต่างจากเดิมอย่างไรบ้าง