主題
題目連結(jié)：
題目大意：
輸入第一列給定一正整數(shù) N （1 ≦ N ≦ 10000），代表座標(biāo)平面上有 N 個(gè)點(diǎn)。接著有 N 列輸入，每列給定兩正整數(shù) x 、 y （1 ≦ x 、 y ≦ 1000），代表這 N 個(gè)點(diǎn)的座標(biāo)。
一點(diǎn) (a, b) 「支配」（Dominant）另一點(diǎn) (c, d) 若且唯若 a > c 且 b > d。試問對於每個(gè)輸入的點(diǎn)，其支配多少的點(diǎn)？即問每個(gè)點(diǎn)的排名（Rank）為何？
範(fàn)例輸入：
5
961 404
640 145
983 888
539 71
437 532
範(fàn)例輸出：
2
1
4
0
0
解題思維：
可用分治法（Divide And Conquer）的經(jīng)典題目。以下為步驟：
一：將所有點(diǎn)按照 x 值由小到大排序，x 值一樣的則將 y 值由大到小排。
二：判斷點(diǎn)的個(gè)數(shù)，如果只有一個(gè)就不須做以下任何事。單一一個(gè)點(diǎn)的排名為 0 。
三：找到所有點(diǎn)的 x 座標(biāo)之中位數(shù)。因?yàn)橐呀?jīng)排序了，所以是一串?dāng)?shù)字中正中間的數(shù)字，偶數(shù)個(gè)數(shù)字則取最靠近的其中一個(gè)即可。然後以此作為分水嶺，將點(diǎn)分為左右兩側(cè)為 L 以及 R。
四：分別遞迴解 L 以及 R 。也就是回到步驟二。
五：合併 L 以及 R 的解——採用類似合併排序（Merge Sort）的方式合併，用兩個(gè)指標(biāo)指向 L 以及 R 的開頭。每次看目前指到的點(diǎn)誰的 y 座標(biāo)較小。如果是 L 方的，則表示接下來的所有剩下的在 R 中的點(diǎn)將支配 L 的該點(diǎn)（因此用一變數(shù) c 儲存目前已經(jīng)有多少的 L 點(diǎn)，c 一開始為 0）；如果是 R 方的，則將 R 該點(diǎn)的排名加上 c（表示其支配了 L 中的 c 個(gè)點(diǎn)）。
做完以上步驟即可得到每個(gè)點(diǎn)的排名。但是因?yàn)楸绢}的輸出是要照原本的輸入順序而輸出排名的，因此我們需要額外紀(jì)錄每個(gè)點(diǎn)原本的索引值。當(dāng)要更新排名時(shí)，就根據(jù)原本的索引值去更新對應(yīng)的排名值，最後便可以直接輸出排名值。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
