7505: [CSES Problem Set] Ferris Wheel
[Creator : ]
Description
There are nn children who want to go to a Ferris wheel, and your task is to find a gondola for each child.
Each gondola may have one or two children in it, and in addition, the total weight in a gondola may not exceed $x$. You know the weight of every child.
What is the minimum number of gondolas needed for the children?
Each gondola may have one or two children in it, and in addition, the total weight in a gondola may not exceed $x$. You know the weight of every child.
What is the minimum number of gondolas needed for the children?
Input
The first input line contains two integers $n$ and $x$: the number of children and the maximum allowed weight.
The next line contains $n$ integers $p_1,p_2,…,p_n$: the weight of each child.
The next line contains $n$ integers $p_1,p_2,…,p_n$: the weight of each child.
Output
Print one integer: the minimum number of gondolas.
Constraints
$1 \leq n \leq 2 \times 10^5$
$1 \leq x \leq 10^9$
$1 \leq p_i \leq x$
$1 \leq x \leq 10^9$
$1 \leq p_i \leq x$
Sample 1 Input
4 10
7 2 3 9
Sample 1 Output
3
每个缆车车厢只能做 $1 \sim 2$ 人，而且总重量不能超过 $10$。
第 $1$ 个人重量是 $7$，座一个缆车车厢。
第 $2$ 和第 $3$ 个人的重量总和为 $2+3=5$，座一个缆车车厢。
第 $3$ 个人重量是 $9$，座一个缆车车厢。
这样一共需要最少 $3$ 个缆车车厢。
第 $1$ 个人重量是 $7$，座一个缆车车厢。
第 $2$ 和第 $3$ 个人的重量总和为 $2+3=5$，座一个缆车车厢。
第 $3$ 个人重量是 $9$，座一个缆车车厢。
这样一共需要最少 $3$ 个缆车车厢。