toi

TOI19 merge - ผสาน (Merge)

🏠 รวมเฉลย TOI19

💎 problem.pdf

🎉 solution.cpp

Binary Search โดยเช็คคำตอบแต่ละครั้งด้วย Binary Search บน Quicksum

ข้อนี้จะมี จะใช้ X[] และ Y[] มาแล้วหาลำดับที่ n-th

ถ้าโจทย์ถามแค่ว่า ให้ int arr[] มาหาว่า idx ที่เท่าไหร่ที่มีผลรวม arr[1..idx] < val ก็หาได้โดยการทำ quicksum ก่อน 1 รอบ แล้ว binary search บนนั้น

สำหรับโจทย์คราวนี้ก็แค่เปลี่ยนจากการใช้ idx เป็นการใช้ค่า position ที่ให้มาตอนแรกแทน

แต่ข้อนี้สมการยากขึ้นไปอีกเพราะ Y[].position จะเปลี่ยนไปตามแต่ละคำถามกลายเป็น Y[].position * alpha + beta แต่สมการ y = ax + b เป็นสมการ linear เพราะงั้นความสามารถในการ binary search ก็ยังใช้ได้อยู่ดี และหา inverse ได้ด้วย y = ax + b กลับสมการ x = (y - b) / a

สรุปเป็นสมการสั้นๆคือ

binary_search([-infinity, infinity]) { |val|
  int count_x = binary_search(X[], val)
  int count_y = binary_search(Y[], (val / beta) - alpha)
  check(count_x + count_y < n_th)?
}