第一回写二分法查找_poj3273
第一次写二分法查找_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实现:
这是我第一次写二分法查找,题目是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; } }