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树的功能。