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 将它插入到解集中。