單調性與順序關係

tags: Competitive Programming Note

在開始介紹需要利用大小關係的事情之前，要先介紹一些跟寫程式比較沒關係的東西。

單調性

單調性是函數的一種性質，簡單來說，若

$f(x)$ 滿足非嚴格遞增或遞減，那我們說

$f(x)$ 滿足單調性，也就是說，對於所有在定義域內的元素

$i<j$，滿足

$f(i)\le f(j)$ 或

$f(i)\ge f(j)$，那

$f(x)$ 就滿足單調性。

舉例來說，

$f(x)=x$ 是一個遞增函數，也就是說，對於任何的實數

$i<j$，都滿足

$f(i)<f(j)$，同理

$f(x)=-x$ 是一個遞減函數，它也滿足單調性。如果有一個函數

$f(x)$，在

$x\ge 5$ 時

$f(x)=1$，否則

$f(x)=0$，那

$f(x)$ 也是一個遞增函數，也滿足單調性。

當函數有了單調的性質，我們就可以利用它來優化搜尋方式。舉例來說，假設我們要找一個

$a$ 滿足

$f(a)=t$，且

$f(x)$ 是一個嚴格遞增函數，如果我們知道

$f(b)<t$，那我們知道對於任何的

$i<b$，

$f(i)$ 都小於

$t$，這樣一來我們就可以確定小於等於

$b$ 的數字都不是我們想找的

$a$，從而縮小搜尋範圍。

順序關係

在確認一個函數是否滿足單調性之前，要先能對定義域內的元素比大小，但函數的定義域並不必要是實數，在競程上，也很常遇到不是數字的東西卻要比大小的狀況。例如數對，也就是 C++ 的 pair，通常在比兩個數對大小時，我們會先比第一項的大小，如果相同，再比第二項的大小，有時則會有更複雜的狀況。

如果你要比較集合內元素的大小，那你需要定義如何比較大小，假設有兩個在定義域內的元素，你要定義它們如何比大小，那你的定義應該要滿足三一律和遞移律，也就是：

• 三一律：對於任兩個元素，它們的關係一定是大於、小於或等於的其中一個。
• 遞移律：對於任三個元素
  $i$、
  $j$、
  $k$，若滿足
  $i<j$ 且
  $j<k$，那也應該滿足
  $i<k$；若
  $i=j$ 且
  $j=k$，那應該滿足
  $i=k$；若
  $i>j$ 且
  $j>k$，那應該滿足
  $i>k$。

確認好你定義的比大小方式滿足這兩項，這樣一來這些元素就有了新的比大小的方式，同時我們也決定了這個集合中的元素應該如何被排序，換句話說，集合內的元素只能按照滿足以上條件的比大小方式來排序。

舉例來說，我們重新定義正整數比較大小的方式：為了避免混淆，我們在關係符號後加上

${}^{\prime }$ 來表示我們定義的新的大小關係。令

$f(x)$ 等於

$x$ 的各個位數相加，例如

$f(123)=6$、

$f(57)=12$，兩個正整數

$i$、

$j$ 的新關係和

$f(i)$、

$f(j)$ 的關係相同，也就是說如果

$f(i)>f(j)$，那

$i{>}^{\prime }j$，小於和等於亦然。

其實這就是重新定義函數定義域元素大小關係，使得函數符合單調性。如果我們要使「

$i$、

$j$ 的新大小關係等同於

$f(i)$、

$f(j)$ 的大小關係」，我們可以知道這樣定義的比較方式一定是滿足三一律和遞移律的，因為我們這樣定義的前提是我們已經有對應域元素比大小的方式，而每個定義域元素又只對應到一個對應域元素上。

但是有的時候，我們不一定可以用這樣的方式來重新決定大小。再看看數對的例子，假設有兩個數對

$p_1=(a,b)$ 和

$p_2=(c,d)$，

$a,b,c,d\in \mathbb{R}$，我們定義：

• 如果
  $a<c$，那
  $p_1<p_2$。
• 如果
  $a>c$，那
  $p_1>p_2$。
• 如果
  $a=c$：
  • 如果
    $b<d$，那
    $p_1<p_2$。
  • 如果
    $b>d$，那
    $p_1>p_2$。
  • 如果
    $b=d$，那
    $p_1=p_2$。

這就是 C++ 中內建 pair 的比較方式。這個比較方式並不是將集合內的元素對應到另一個可比較大小的集合裡的元素，來判斷元素的大小關係，所以我們必須自己證明這個比較方式滿足遞移律和三一律了：

三一律很簡單，可以看到在定義中，我們有定義所有狀況下的結果了，我們知道兩個實數

$a,b$ 的關係必然符合大於、小於或等於的其中一項，也就是實數比較滿足三一律，因此我們可以得出我們的數對比較方式滿足三一律。

接下來是遞移律：有三個數對

$p_1=(x_1,y_1)$、

$p_2=(x_2,y_2)$、

$p_3=(x_3,y_3)$，令

$p_1>p_2$ 且

$p_2>p_3$，我們要證明

$p_1>p_3$，可以分成幾個狀況：

• $x_1>x_2$
  • $x_2>x_3$：可知
    $x_1>x_3$，得出
    $p_1>p_3$。
  • $x_2=x_3$，
    $y_2>y_3$：可知
    $x_1>x_3$，得出
    $p_1>p_3$。

小於和等於的證法就同理，這樣一來我們就可以確定這樣的比較方式是合法的。

在 C++ 的標頭檔 algorithm 中，有一個 function sort() 是用來排序的，它的複雜度是

$O(n\log n)$，同時它也有定義比大小方式的功能：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 已經有內建的 < 運算子做這個比較了。

練習題

APCS 20171018 p4/ZeroJudge c471

在這題中，對於任兩個物品

$i$、

$j$，如果

$i$ 在

$j$ 之上，在取用

$j$ 時，移動

$i$ 的成本是

$w(i)\times f(j)$，我們希望它盡量小一點。

對於兩個相異物品

$a$ 和

$b$，它們一定有其中一個是在另一個下面，所以總成本一定會需要加上

$w(a)\times f(b)$ 或

$w(b)\times f(a)$，如果可以都選較小那個就簡單多了，但能這樣做的前提是，對於任兩個物品，我們都能選擇較小的那個成本，而不會互相衝突，也就是說：對於三個相異物品

$a$、

$b$、

$c$，如果我們希望

$a$ 在

$b$ 的上面，且希望

$b$ 在

$c$ 的上面，那我們也應該要希望

$a$ 在

$c$ 的上面，可以發現這就是遞移律。

令

$g(x,y)=w(x)\times f(y)$，也就是

$x$ 在

$y$ 之上，取用

$y$ 時移動

$x$ 所消耗的成本，我們要證明的是：對於任三個物品

$a$、

$b$、

$c$，如果

$g(a,b)<g(b,a)$ 且

$g(b,c)<g(c,b)$，那應該滿足

$g(a,c)<g(c,a)$。

如果

$g(i)<g(j)$，那表示

$w(i)\times f(j)<w(j)\times f(i)$，也就是

$\frac{w(i)}{f(i)}<\frac{w(j)}{f(j)}$，因此我們可以令

$h(x)=\frac{w(x)}{f(x)}$，如果

$i$ 要在

$j$ 上面，那

$h(i)<h(j)$，因此我們可以重新安排整數的大小關係，以使得

$h(x)$ 滿足單調性。

如果看不懂的話，只要把上上段的不等式展開再移項就可以得到相同結論了。總而言之，你可以利用

$g(i)<g(j)$ 這樣的關係來排序數字，就可以得出這題的答案了。