網頁

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。