A.Nth Largest Value
PKU 3781 http://poj.org/problem?id=3781
水題，求10個數(shù)中第3大的數(shù)。
B.Equal Sum Partitions
PKU 3782 http://poj.org/problem?id=3782
題意：給定一個M(M <= 10000)個元素的序列，將它切割成K塊，每塊的和相等，求最大的K。
題解：枚舉。
首先，切成K塊，每塊和相等，那么這個和必定是M個元素總和的一個因子，那么可以枚舉第一個塊的長度（M種），判斷當前塊的和是否能被所有數(shù)的總和整除，如果可以，順序判斷可行性，看似復雜度是O(M^2)，但是能否整除這個剪枝可以篩選掉絕大部分情況。
C.Balls
PKU 3783 http://poj.org/problem?id=3783
題意：給定B (B <= 50) 個一樣的球，從 M (M <= 1000) 層樓上一個一個往下扔，存在某個樓層K，使得低于它的樓層往下扔球，球不會碎，在第K層扔下去會碎。求最壞情況下，需要扔幾次才能確定這個K。
題解：動態(tài)規(guī)劃。
令DP[i][j]表示總樓層為i，持有j個球時，最壞情況需要的次數(shù)；
那么如果從k ( 1 <= k <= i) 層進行扔球，有兩種情況：
1) 如果球不碎，則還需要進行DP[i-k][j]次測試（向更高的樓層進發(fā)）；
2) 如果球碎，那么還可以進行的次數(shù)為DP[k-1][j-1] （損失了一個球）；
由于要考慮最壞情況，所以每次測試必須取(1) (2)中的大者+1，每次選定一個樓層，使得這個樓層往下扔球的結(jié)果的最大值最小，也即狀態(tài)轉(zhuǎn)移方程為：
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)的序列，每次奇數(shù)位的數(shù)讀入的時候計算前面整個序列的中位數(shù)。
題解：二分 + 樹狀數(shù)組。
由于數(shù)字是int32范圍，所以首先需要將所有數(shù)離散到下標，枚舉每一個數(shù)字讀入，將對應位的數(shù)字下標插入到樹狀數(shù)組中，每當讀到奇數(shù)個的時候，利用樹狀數(shù)組的成端求和的性質(zhì)，如果要找第K大的數(shù)，那么就二分一個答案，然后查詢樹狀數(shù)組，如果求和大于等于K，表示是一個候選解（因為要保證大于等于K的數(shù)最小，才是第K大的數(shù)），反復二分，直到找到最小的值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位之后最小的數(shù)，那么將A[i]和A[j]進行交換，然后將A[i+1]到末尾的元素進行一次不降序排序，最后得到的串就是解。
F.Adjacent Bit Counts
PKU 3786 http://poj.org/problem?id=3786
題意：求長度為n的二進制整數(shù)中，相鄰兩個1的對數(shù)有k對（可重復使用）的整數(shù)個數(shù)。
題解：動態(tài)規(guī)劃。
令長度為n，相鄰1的對數(shù)為k的數(shù)的個數(shù)為DP[n][k]，其中以0結(jié)尾的為DP[n][k][0]，以1結(jié)尾的為DP[n][k][1]，那么 DP[n][k] = DP[n][k][0] + DP[n][k][1]；
并且有如下狀態(tài)轉(zhuǎn)移方程：
1) 長度為n-1的二進制數(shù)在末尾加上一個0，相鄰1的對數(shù)不變，所以有：
DP[n][k][0] = DP[n-1][k][0] + DP[n-1][k][1];
2) 長度為n-1的二進制數(shù)在末尾加上一個1，相鄰1的對數(shù)取決于，第n-1位是0還是1，當?shù)?/span>n-1位是1，相鄰1的對數(shù)+1；當?shù)?/span>n-1位是0，相鄰1的對數(shù)不變，所以有：
DP[n][k][1] = DP[n-1][k][0] + DP[n-1][k-1][1];
并且初始狀態(tài)下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
題意：給定一個凸多邊形，求它內(nèi)部所有的水平線段。
題解：從多邊形第一個點的y坐標開始，遞減枚舉水平線段的y坐標，分別和多邊形的n條邊進行求交點；
1) 如果水平線段和多邊形某條邊共線，說明正好到了多邊形的邊緣，無須往下枚舉，跳出循環(huán)。
2) 如果水平線段和多邊形小于一個交點，那么當y軸再次減小的時候，必然沒有交點，也無須繼續(xù)枚舉。
3) 否則，將左端點坐標取上整x1，右端點取下整x2，如果x1 <= x2 將它插入到解集中。