2.分块

题目描述

给你 n 个非负整数，把它们按顺序分成 m 块，每块长度都是 floor(n/m)，(即 n/m 向下取整），这意味着可能会忽略后面多余的一些数。 现在你要从每块中选取一个最大值。并且所有选取的 m 个数的和大于 k。请你找出最小的分块数 m.

输入输出格式

输入格式：

输入包含多组测试数据。 每组测试数据： 第一行包含两个数字 n 和 k，表示 n 个数和限制 k 。 第二行包含 n 个数字 a1,a2,...an。 读到两个 -1 直接结束，不需要进行额外处理。

输出格式：

对于每组测试数据，输出一行表示最小的分块数 m，如果找不到则输出 -1。

输入输出样例

输入样例#1：

11 300 7 100 7 101 100 100 9 100 100 110 110 -1 -1

输出样例#1：

3

补充说明

【数据范围】

对于 40% 的数据， n<=100，k<=1000。 对于 100% 的数据，n<=200000，k<=1e9 ，0<=ai<=1000，数据组数<=10。

时间限制：1s 空间限制：512M

玄关