[TIOJ1403][CEOI 2003]16 - 賽車 (The Race)

Sylveon

原題：http://www.ceoi2003.de/www/downloads/therace-en.pdf
TIOJ：http://tioj.ck.tp.edu.tw/problems/1403
HOJ：http://hoj.twbbs.org/judge/problem/view/16


AC：http://tioj.ck.tp.edu.tw/submissions/11845

本問題分為兩問題，第一問題可用BIT完成，不過[tex]V%5Cleq100[/tex]，暴力加一加也行，重點在第二部分，當然我們不能枚舉所有pair，這樣肯定超時。此時我們可以採用模似法，反正超車一定是前一輛車超過下一輛車，我們可以先線性掃瞄有哪一些車子要超過後面的車子，放入一個priority queue中依照相遇時間以及位置作為基準一一拿出，每次拿出後，更新這兩台車子的位置，以及新出來的超車關係，就能完成這題了。

[sojcodepad]281e9ac1[/sojcodepad]