A.Nth Largest Value
PKU 3781 http://poj.org/problem?id=3781

水题，求10个数中第3大的数。

B.Equal Sum Partitions
PKU 3782 http://poj.org/problem?id=3782

题意：给定一个M(M <= 10000)个元素的序列，将它切割成K块，每块的和相等，求最大的K。

题解：枚举。

首先，切成K块，每块和相等，那么这个和必定是M个元素总和的一个因子，那么可以枚举第一个块的长度（M种），判断当前块的和是否能被所有数的总和整除，如果可以，顺序判断可行性，看似复杂度是O(M^2)，但是能否整除这个剪枝可以筛选掉绝大部分情况。

C.Balls
PKU 3783 http://poj.org/problem?id=3783

题意：给定B (B <= 50) 个一样的球，从 M (M <= 1000) 层楼上一个一个往下扔，存在某个楼层K，使得低于它的楼层往下扔球，球不会碎，在第K层扔下去会碎。求最坏情况下，需要扔几次才能确定这个K。

题解：动态规划。

令DP[i][j]表示总楼层为i，持有j个球时，最坏情况需要的次数；

那么如果从k ( 1 <= k <= i) 层进行扔球，有两种情况：

1) 如果球不碎，则还需要进行DP[i-k][j]次测试（向更高的楼层进发）；

2) 如果球碎，那么还可以进行的次数为DP[k-1][j-1] （损失了一个球）；

由于要考虑最坏情况，所以每次测试必须取(1) (2)中的大者+1，每次选定一个楼层，使得这个楼层往下扔球的结果的最大值最小，也即状态转移方程为：

DP[i][j] = Min( DP[i][j], Max(DP[i-k][j], DP[k-1][j-1]) + 1 );

Pku上有道和这题想法类似的题：http://poj.org/problem?id=1243

D.Running Median
PKU 3784 http://poj.org/problem?id=3784

题意：一个长度为M(M <= 9999)的序列，每次奇数位的数读入的时候计算前面整个序列的中位数。

题解：二分 + 树状数组。

由于数字是int32范围，所以首先需要将所有数离散到下标，枚举每一个数字读入，将对应位的数字下标插入到树状数组中，每当读到奇数个的时候，利用树状数组的成端求和的性质，如果要找第K大的数，那么就二分一个答案，然后查询树状数组，如果求和大于等于K，表示是一个候选解（因为要保证大于等于K的数最小，才是第K大的数），反复二分，直到找到最小的值V满足sum(V) >= K，时间复杂度O(2 *M * log(M) )。

E.The Next Permutation
PKU 3785 http://poj.org/problem?id=3785

题意：给定一个可重复元素的排列A[i]，求下一个排列。

题解：从后往前扫描，对于第i个元素A[i]，如果能够找到一个j，使得A[j] > A[i]，并且满足A[j]是继第i位之后最小的数，那么将A[i]和A[j]进行交换，然后将A[i+1]到末尾的元素进行一次不降序排序，最后得到的串就是解。

F.Adjacent Bit Counts
PKU 3786 http://poj.org/problem?id=3786

题意：求长度为n的二进制整数中，相邻两个1的对数有k对（可重复使用）的整数个数。

题解：动态规划。

令长度为n，相邻1的对数为k的数的个数为DP[n][k]，其中以0结尾的为DP[n][k][0]，以1结尾的为DP[n][k][1]，那么 DP[n][k] = DP[n][k][0] + DP[n][k][1]；

并且有如下状态转移方程：

1) 长度为n-1的二进制数在末尾加上一个0，相邻1的对数不变，所以有：

DP[n][k][0] = DP[n-1][k][0] + DP[n-1][k][1];

2) 长度为n-1的二进制数在末尾加上一个1，相邻1的对数取决于，第n-1位是0还是1，当第n-1位是1，相邻1的对数+1；当第n-1位是0，相邻1的对数不变，所以有：

DP[n][k][1] = DP[n-1][k][0] + DP[n-1][k-1][1];

并且初始状态下DP[0][0][0] = 1, DP[0][0][1] = 0

G.Convex Hull of Lattice Points

PKU 3787 http://poj.org/problem?id=3787
题意：凸包。

题解：Graham扫描法求解即可。

H.Interior Points of Lattice Polygons

PKU 3788 http://poj.org/problem?id=3788
题意：给定一个凸多边形，求它内部所有的水平线段。

题解：从多边形第一个点的y坐标开始，递减枚举水平线段的y坐标，分别和多边形的n条边进行求交点；

1) 如果水平线段和多边形某条边共线，说明正好到了多边形的边缘，无须往下枚举，跳出循环。

2) 如果水平线段和多边形小于一个交点，那么当y轴再次减小的时候，必然没有交点，也无须继续枚举。

3) 否则，将左端点坐标取上整x1，右端点取下整x2，如果x1 <= x2 将它插入到解集中。