1.5　練習題

習題1-1

題目來源：POJ 2388。

題目類型：排序算法。

解題思路：為一個序列求中位數，排序后取中間的數即可，通過堆排序可解。

習題1-2

題目來源：HDOJ 2852。

題目類型：樹狀數組，二分法。

解題思路：給定一個容器，里面存放各種數值，規定三個操作：一個是在容器中增加一個數值；一個是在容器中刪掉一個數值；一個是詢問容器中比a大的數中的第k個數，并將其輸出。樹狀數組可以實現點更新，對于詢問容器中比a大的第k個數，可以通過二分法答案求得。

習題1-3

題目來源：POJ 3016。

題目類型：左傾堆，動態規劃。

解題思路：給定n個數的序列A，將其分成k個區間，改變其中的一些數使得每個區間嚴格單調，求改動的最小代價。此題和前面的例題相比，要求嚴格遞增，所以首先需要計算A[i]-i。將[i,j]區間調整成單調序列的代價表示為cost[i][j]，顯然將前i部分分成k塊單調區間所需要的最小代價就是dp[k][i]= min{dp[k-1][j]+cost[j+1][i]，（j<i）}，需要求cost數組，這樣就轉化為前面的例題。在Treap維護中位數合并時，如果當前塊的數量為偶數，答案不變，否則答案增加。

習題1-4

題目來源：HDOJ 4557。

題目類型：Treap。

解題思路：人才庫存儲一些人員信息，每人有一個能力值，公司在招聘時有一個能力值的最低要求，優先把能力值低的人才推薦過去；如果依然有多名人員符合要求，就把其中最早來求職的那位學生推薦過去。用Treap保存人員信息，每個節點有能力值和時間兩個人信息，排序時需要考慮兩個信息。姓名可以用map映射到時間。

習題1-5

題目來源：POJ 3580。

題目類型：Splay樹。

解題思路：題目要求實現一種數據結構，支持6種操作：①add x,y D：第x個數到第y個數之間的數每個加D；②reverse x y：第x個數到第y個數之間的數全部翻轉；③revolve x y T：第x個數到第y個數之間的數向后循環流動T次，即后面T個數變成子序列的最前面T個，前面的被擠到后面；④insert xP：在第x個數后面插入一個數P；⑤delete x：刪除第x個數；⑥min x，y：求第x個數到第y個數之間的最小數字。很明顯的數據結構題，只有強大的Splay樹才能實現這么多功能。本習題涉及區間更新及單點插入、刪除等操作，能全面地了解Splay樹的功能。