Competitive Programming Note
在開始介紹需要利用大小關係的事情之前,要先介紹一些跟寫程式比較沒關係的東西。
單調性是函數的一種性質,簡單來說,若
舉例來說,
當函數有了單調的性質,我們就可以利用它來優化搜尋方式。舉例來說,假設我們要找一個
在確認一個函數是否滿足單調性之前,要先能對定義域內的元素比大小,但函數的定義域並不必要是實數,在競程上,也很常遇到不是數字的東西卻要比大小的狀況。例如數對,也就是 C++ 的 pair,通常在比兩個數對大小時,我們會先比第一項的大小,如果相同,再比第二項的大小,有時則會有更複雜的狀況。
如果你要比較集合內元素的大小,那你需要定義如何比較大小,假設有兩個在定義域內的元素,你要定義它們如何比大小,那你的定義應該要滿足三一律和遞移律,也就是:
確認好你定義的比大小方式滿足這兩項,這樣一來這些元素就有了新的比大小的方式,同時我們也決定了這個集合中的元素應該如何被排序,換句話說,集合內的元素只能按照滿足以上條件的比大小方式來排序。
舉例來說,我們重新定義正整數比較大小的方式:為了避免混淆,我們在關係符號後加上
其實這就是重新定義函數定義域元素大小關係,使得函數符合單調性。如果我們要使「
但是有的時候,我們不一定可以用這樣的方式來重新決定大小。再看看數對的例子,假設有兩個數對
這就是 C++ 中內建 pair 的比較方式。這個比較方式並不是將集合內的元素對應到另一個可比較大小的集合裡的元素,來判斷元素的大小關係,所以我們必須自己證明這個比較方式滿足遞移律和三一律了:
三一律很簡單,可以看到在定義中,我們有定義所有狀況下的結果了,我們知道兩個實數
接下來是遞移律:有三個數對
小於和等於的證法就同理,這樣一來我們就可以確定這樣的比較方式是合法的。
在 C++ 的標頭檔 algorithm
中,有一個 function sort()
是用來排序的,它的複雜度是 sort(iterator begin, iterator end, Comaper compare)
,compare
可以是函數或 lambda 表達式,要有兩個傳入值,如果第一個值應該排在第二個值前面就回傳 true
,否則就回傳 false
,如果兩個相等,也應該回傳 false
,因為它們沒有必然地誰應該在誰前面。
用剛剛的數對來舉例,這邊直接使用 C++ 內建的 pair,我們要使較小的那個排在前面:
bool comp(pair<int, int> a, pair<int, int> b){
return a.first < b.first ? true : a.second < b.second;
}
接著有一個 vector<pair>
叫 a
,用 sort(a.begin(), a.end(), comp)
就可以排序了。如果不填 compare
,那預設會用 <
運算子來比較,所以也可以直接實作物件的 <
運算子,pair
已經有內建的 <
運算子做這個比較了。
在這題中,對於任兩個物品
對於兩個相異物品
令
如果
如果看不懂的話,只要把上上段的不等式展開再移項就可以得到相同結論了。總而言之,你可以利用