რაგბი - ანალიზი

ავტორი: lukamosiashvili

თარიღი: 26.12.2018 15:19


დავასორტიროთ რაგბისტების მასივი სიმაღლის მიხედვით.

დავაფიქსიროთ  ყველა (Y;Z) წყვილი და დავითვალოთ რამდენი შესაძლო ვარიატია X-ის არჩევის. ამისთვის გამოვიყენოთ ორობითი ძებნა:

თუ ვართ რაღაც X1 მნიშვნელობაზე შეჩერებულები და Z-Y<Y-X 1ანუ X1 უფრო მარჯვნივ უნდა ავიღოთ, თუ Z-Y>(Y-X1)*2 მაშინ X1 ცოტა უფრო მარცხნივ უნდა ავიღოთ.

ეს ამოხსნა იმუშავებს O(n*n*logn)-ში;

ჩემი კოდი შეგიძლიათ ნახოთ ლინკზე: https://www.informatics.ge/status/submission/591



1

კომენტარები