pretoi19

Oranges สวนส้มคู่แข่งเจแปน

🎉 solution.cpp

ข้อสวนส้มเราวัดการมองเห็นหรือไม่เห็น ซ้อนทับกันหรือไม่ทับกัน ตาม slope ของจุดนั้นๆกับ (0,0)

เพราะงั้นขั้นแรกเราควรแปลงข้อมูลให้อยู่ในพิกัดที่เราจะใช้งานได้ง่ายๆนั้นคือ องศา นั้นเอง

#include <cmath>
slope = atan2(x, y);

ต่อมาเราต้องการลบแผงส้มจำนวนน้อยสุดที่ลบแล้วทำให้เห็นแผงส้มทุกอัน ก็คิดในมุมกลับกันว่า หาว่าแผงส้มที่เห็นมากสุดโดยไม่ทับกันคือเท่าไหร่ แล้วเอาจำนวนแผงส้มทั้งหมดมาลบ จะได้ แผงส้มจำนวนน้อยสุดที่ลบแล้วทำให้เห็นแผงส้มทุกอัน

ถ้าคิดได้แบบนี้ก็จะตรงกับโจทย์ Interval scheduling เป็นโจทย์ classic หมวด Greedy Algorithm คือหากให้เวลาเริ่ม/จบของแต่ละคาบเรียนมา ให้หาว่าเราสามารถเข้าร่วมคาบเรียนได้มากสุดเท่าไหร่โดยไม่สามารถเรียนทับซ้อนกันได้.

วิธีทำของ Interval scheduling คือให้เราเรียนวิชาที่เลิกเรียนไวๆ จะได้มีเวลามาหาคลาสเรียนถัดไปได้เร็วกว่าคนอื่น. ใช้เวลา O(n log n) ในการ sort ตามเวลาเลิกเรียน

ถ้าทำตามข้างบนได้ก็เหมือนจะ solve ได้แล้ว แต่!!!

testcase มีดักไว้ว่า ถ้าเราใช้ slope ตรงๆ จะมีค่าที่ slope มันใกล้กันมากๆจนคอมปัดเศษทิ้ง ทำให้ค่าผิดได้ ดังนั้นสุดท้ายแล้วเราก็เก็ยค่าเป็น slope ตรงๆไม่ได้อยู่ดีต้องเก็บเป็น Point(x, y) แทน แล้วเขียน function เปรียบเทียบ slope เอาแทน

Point a, b;
// เปรียบเทียบ slope ของ a, b
return slope(a) < slope(b)
=
return (a.x / a.y) < (b.x / b.y)
=
return (a.x * by.y) < (b.x * a.y)

ถ้าทำได้หมดนี้ก็ 100% ละครับ