第一次写二分法查找_poj3273
这是我第一次写二分法查找，题目是poj上的,http://poj.org/problem?id=3273
一开始看到这个题目，对于我这个acm菜鸟来说，这个题目就是我想破天了，也想不到这种方法。下面把这道题的题意，解题的思想和Java实现记录下来。大家批评一下。
（1）题意： 给你天数N(1 ≤ N ≤ 100,000)，和每天需要花的钱（存放在数组中），让你把这些天分成M(1 ≤ M ≤ N)份（每份都是连续的天），要求每份的和最大值尽量小，输出这个和。
（2）思想：二分查找。让数组中的最大值为左界，数组的和为右界。左界的含义是将整个数组分成N块，那么和的最大值就是数组元素中的最大值。右界的含义是将整个数组当做一块，那么最大值就是所有数字之和。那么在左右界中（含左右界）的数肯定有一个是解。接着进行二分搜索：给定一个数count，从数组首元素开始叠加，超出count那么分块数i加1，那么这么遍历一遍后能得到以count为解所需的分块数，要是i小于M，说明count给的大了，反之count给小了。
(3) Java实现：

package id3000_3999;import java.util.Scanner;/** * 5608K 2204MS ac */public class Id3273 {static int[] arr;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int M = sc.nextInt();arr = new int[N];int count = 0, left = 0, right = 0;while (count < N) {arr[count] = sc.nextInt();if (arr[count] > left)left = arr[count];right += arr[count];count++;}while (left < right) {count = (left + right) >> 1;int i = deal(count);if (i < M) {right = count;} else {left = count + 1;}}System.out.println(left);}/**     * @return i 以countwield解所需的分块数     */private static int deal(int count) {int i = 0， len = arr.length,sum = 0;for (int j = 0; j < len; j++) {sum += arr[j];if (sum > count) {i++;sum = arr[j];}}return i;}}