二分习题
数列分段 Section II
题目描述
对于给定的一个长度为N的正整数数列 $A_{1\sim N}$,现要将其分成 $M$($M\leq N$)段,并要求每段连续,且每段和的最大值最小。
关于最大值最小:
例如一数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段。
将其如下分段:
第一段和为 $6$,第 $2$ 段和为 $9$,第 $3$ 段和为 $1$,和最大值为 $9$。
将其如下分段:
第一段和为 $4$,第 $2$ 段和为 $6$,第 $3$ 段和为 $6$,和最大值为 $6$。
并且无论如何分段,最大值不会小于 $6$。
所以可以得到要将数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段,每段和的最大值最小为 $6$。
输入格式
第 $1$ 行包含两个正整数 $N,M$。
第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$,含义如题目所述。
输出格式
一个正整数,即每段和最大值最小为多少。
样例 #1
样例输入 #1
1 | 5 3 |
样例输出 #1
1 | 6 |
提示
对于 $20\%$ 的数据,$N\leq 10$。
对于 $40\%$ 的数据,$N\leq 1000$。
对于 $100\%$ 的数据,$1\leq N\leq 10^5$,$M\leq N$,$A_i < 10^8$, 答案不超过 $10^9$。
题解
思路
这道题球的是最大值的最小,所以要用到二分,根据题意,这道题的和最小为数组中的某一个数的最大值,最大为整个数组的和。因此,我们确定二分的范围,让左值的等于数组中的最大值,右值取得整个数组的和。然后我们需要的如何分段,当我们让遍历数组,如果每次相加小于中间值,就接着相加,否则就重开一段,再让变量当计数器去++,这样就有两段了,以此类推。直到变量大于等于段数。
代码
1 |
|
[NOIP2015 提高组] 跳石头
题目背景
NOIP2015 Day2T1
题目描述
一年一度的“跳石头”比赛又要开始了!
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 $N$ 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 $M$ 块岩石(不能移走起点和终点的岩石)。
输入格式
第一行包含三个整数 $L,N,M$,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。保证 $L \geq 1$ 且 $N \geq M \geq 0$。
接下来 $N$ 行,每行一个整数,第 $i$ 行的整数 $D_i\,( 0 < D_i < L)$, 表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。
输出格式
一个整数,即最短跳跃距离的最大值。
样例 #1
样例输入 #1
1 | 25 5 2 |
样例输出 #1
1 | 4 |
提示
输入输出样例 1 说明
将与起点距离为 $2$ 和 $14$ 的两个岩石移走后,最短的跳跃距离为 $4$(从与起点距离 $17$ 的岩石跳到距离 $21$ 的岩石,或者从距离 $21$ 的岩石跳到终点)。
数据规模与约定
对于 $20\%$的数据,$0 \le M \le N \le 10$。
对于 $50\%$ 的数据,$0 \le M \le N \le 100$。
对于 $100\%$ 的数据,$0 \le M \le N \le 50000,1 \le L
\le 10^9$。
题解
思路
这道题求的是最短距离的最大,因此,我们需要二分,在这里我们将取得中间值与每次数组的前后差值去比较,小于中间值,我们就将其变量tot++,否则让数组的下一个接着减去上一个。直到tot小于移走岩石的数量。然后再二分中让符合结果的答案等于中间值,直到缩短区间后取得的最大中间值即为答案。
代码
1 |
|
书的复制
题目背景
大多数人的错误原因:尽可能让前面的人少抄写,如果前几个人可以不写则不写,对应的人输出 0 0
。
不过,已经修改数据,保证每个人都有活可干。
题目描述
现在要把 $m$ 本有顺序的书分给 $k$ 个人复制(抄写),每一个人的抄写速度都一样,一本书不允许给两个(或以上)的人抄写,分给每一个人的书,必须是连续的,比如不能把第一、第三、第四本书给同一个人抄写。
现在请你设计一种方案,使得复制时间最短。复制时间为抄写页数最多的人用去的时间。
输入格式
第一行两个整数 $m,k$。
第二行 $m$ 个整数,第 $i$ 个整数表示第 $i$ 本书的页数。
输出格式
共 $k$ 行,每行两个整数,第 $i$ 行表示第 $i$ 个人抄写的书的起始编号和终止编号。 $k$ 行的起始编号应该从小到大排列,如果有多解,则尽可能让前面的人少抄写。
样例 #1
样例输入 #1
1 | 9 3 |
样例输出 #1
1 | 1 5 |
提示
$1\le k \le m \le 500$。
题解
思路
这题求得是抄书最多页的人用时最少,既求最大值的最小,因此用到二分答案的思想,然后这道题为了让前面的人少抄,因此就要让后面的人多抄,所以从后往前遍历,所以要倒序遍历。然后将其分成m段,且每段的和不超过最优解s。然后再二分查找,二分的时候最低是数组中最大值,最高为整个数组的和。输出的时候,因为考虑到时倒序输入,因此需要我们倒序输出,输出的时候要终止的下标比起始的下标大1。
代码
1 |
|