http://poj.org/problem?id=3273
(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;
}
}
分享到:
相关推荐
此程序可实现二分查找算法,采用的是C编程。
数值分析中用二分法求解函数值,本资料正是二分法求函数值的MATLAB代码
一组从小到大排列的数据用二分法查找指定数据
Matlab 编辑的 高斯 二分法 割线法 牛顿法
通过10K3435查表获取温度值,分压电阻10K,可以精确的测量范围-40到80℃。由于热敏最小电流到0.2mA因此不能使用过小的分压电阻
C语言编程学习,使用二分法查找最大/最小数据
c 二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法...
二分查找实现,修改上下界缩小范围获得正确答案
写出二分法查找算法函数实现。
定义任意长度数组,排好序后按二分查找法查找元素
C语言实现的二分法快速查找|二分法排序|二分法查找C#
二分法查找 *进行二分法查找的前提是数组已有序 *查找范围的上下界
计算方法,二分法,弦截法应用。对于区间[a,b]上连续不断且f(a)·f(b)<0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值的方法。
——二分法查找 目录 课程导入 1 清楚并牢记二分法的实现条件 2 理解二分法的实现思路 3 读懂二分法的实现代码 数组的查找——二分法查找 也称拆半查找法,是一种高效的查找方法,前提条件是数组元素必须已经按升序...
二分法查找法
二分法(dichotomie) 即一分为二的方法. 设[a,b]为R的闭区间. 逐次二分法就是造出如下的区间序列([an,bn]):a0=a,b0=b,且对任一自然数n,[an+1,bn+1]或者等于[an,cn],或者等于[cn,bn],其中cn表示[an,bn]的...
最优化算法中的二分法,是用MATLAB实现的,经过调试的
其中包含牛顿迭代法法,二分法,牛顿下山法 最优化求解的方法
易语言有序二分法查找源码,有序二分法查找,算法_二分法
给定的表中用二分法查找指定数 给定的表中用二分法查找指定数 给定的表中用二分法查找指定数