想法：
使用bubble sort時候每交換一次逆序數就+1，最後由逆序數小到大輸出。至於求逆序數更快的算法可參考UVa 10810 Ultra-Quicksort。
2014年1月2日 星期四
2013年12月29日 星期日
POJ 3067 Japan
本題東邊有N個城市，西邊有M個城市，現在欲蓋多條高速公路連接東西邊，求路線的交點數。
ps.不會有三邊共點的情形
struct city{
int e; // 存東邊城市編號
int w; // 存西邊城市編號
}
想法1：每次讀入(e,w)時(設第k次)就檢查(k-1)次之前所有情況，若city[k-1].e<city[k].e，則city[k-1].w>city[k].w才會有交點，反之。此算法為O(n^2)會TLE。
想法2: 可依e由小到大(若e相等則依w小到大排)將city[K]排序，此時將只討論city[k-1].e<city[k].e的情況，只要檢察前(k-1)次的w值大於第k次的w值的總和就是解答，但如果又用兩個for loop來跑又變成O(n^2)的算法，本題可簡化為求city[K]的逆序數，使用mergesort求逆序數(可參考UVa 10810)，此算法為O(nlgn)會AC。
訂閱：
文章 (Atom)