A7082 | $【ZZSR #1】完美储存$

时间限制2s

内存限制128MB

通过 / 提交0/0

题目描述

wmg 想让你帮他解决内存危机。 --- wmg 有很多硬盘，初始时所有硬盘为空。为了方便起见，本题中所有的内存单位统一为 MB 。每个硬盘的内存空间为 $S$。 现在 wmg 有 连续的 $n$ 个文件要储存。对于第 $i$ 个文件需要占用 $a_i$ 的内存。每次 wmg 会选择当前 剩余容量最大的 硬盘，然后将这个文件存储进去。 显然如果有多个剩余容量最大的硬盘时存选择哪一个硬盘并没有影响。 需要注意的是，你 不可以 改变文件的存储顺序，即处理第 $i$ 个文件时，前 $i-1$ 个文件应该全部储存完毕。 如果在存储某一个文件时出现了硬盘内存不够无法存储的情况，我们判定这一次存储失败，反之成功。现在问你最少需要多少个硬盘使得存储可以成功，即求出满足条件：$k$ 个硬盘存储成功，$k-1$ 个硬盘存储失败的最小的 $k$。

输入格式

本题数据使用多组输入输出，第一行输入一个正整数 $T$ 表示数据组数。 对于每组数据输入共两行： 第一行输入两个正整数 $n,S$。 第二行输入 $n$ 个正整数 $a_i$。

输出格式

输出共 $T$ 行，对于每组数据输出一行一个正整数表示最少需要的硬盘数量，即最小的 $k$。

输入输出样例

输入 #1

2
8 20
4 6 5 1 10 8 6 9
4 2
1 1 1 1

输出 #1

4
2

为了方便描述，如果有剩余容量相同的硬盘，这个样例解释统一用靠前的来存。 对于第一组测试数据： 如果使用四个硬盘，初始时这些硬盘的 剩余容量 分别为20 20 20 20 - 第一个文件：此时剩余容量20 20 20 20，剩余最大的是第一个，$20>4$，可以存储，容量变为16 20 20 20。 - 第二个文件：此时剩余容量16 20 20 20，剩余最大的是第二个，$20>6$，可以存储，容量变为16 14 20 20。 - 第三个文件：此时剩余容量16 14 20 20，剩余最大的是第三个，$20>5$，可以存储，容量变为16 14 15 20。 - 第四个文件：此时剩余容量16 14 15 20，剩余最大的是第四个，$20>1$，可以存储，容量变为16 14 15 19。 - 第五个文件：此时剩余容量16 14 15 19，剩余最大的是第四个，$19>10$，可以存储，容量变为16 14 15 9。 - 第六个文件：此时剩余容量16 14 15 9，剩余最大的是第一个，$16>8$，可以存储，容量变为8 14 15 9。 - 第七个文件：此时剩余容量8 14 15 9，剩余最大的是第三个，$15>6$，可以存储，容量变为8 14 9 9。 - 第八个文件：此时剩余容量8 14 9 9，剩余最大的是第二个，$14>9$，可以存储，最终8 5 9 9。 而若使用三个硬盘：初始时剩余容量为20 20 20 - 第一个文件：此时剩余容量20 20 20，剩余最大的是第一个，$20>4$，可以存储，剩余容量16 20 20。 - 第二个文件：此时剩余容量16 20 20，剩余最大的是第二个，$20>6$，可以存储，剩余容量16 14 20。 - 第三个文件：此时剩余容量16 14 20，剩余最大的是第三个，$20>5$，可以存储，剩余容量16 14 15。 - 第四个文件：此时剩余容量16 14 15，剩余最大的是第一个，$16>1$，可以存储，剩余容量15 14 15。 - 第五个文件：此时剩余容量15 14 15，剩余最大的是第一个，$15>10$，可以存储，剩余容量5 14 15。 - 第六个文件：此时剩余容量5 14 15，剩余最大的是第三个，$15>8$，可以存储，剩余容量5 14 7。 - 第七个文件：此时剩余容量5 14 7，剩余最大的是第二个，$14>6$，可以存储，剩余容量5 8 7。 - 第八个文件：此时剩余容量5 8 7，剩余最大的是第二个，$8<9$，不能存储。 由此可见，至少需要 $4$ 个硬盘，答案为 $4$。 友情提示 建议选手使用快读快写。 数据范围 对于 $20\%$ 的数据，保证 $1\le n \le 10^2$。 对于 $40\%$ 的数据，保证 $1\le n \le 10^3$。 对于 $100\%$ 的数据，保证 $1\le n \le 10^5,1\le S \le 10^9,1\le a_i \le S,T\le 10$。

C++ 编辑器

输入

输出

A7082 | 【ZZSR #1】完美储存

题目描述

输入格式

输出格式

输入输出样例

友情提示

数据范围

A7082 | $【ZZSR #1】完美储存$