题目详情题解（0）讨论（0）提交记录（0）

AT_ddcc2017_qual_c.収納

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 NN 根木棒，第 ii 根木棒的长度为 LiL_i。

现在需要将这些木棒收纳到长度为 CC 的收纳盒中。

每个收纳盒最多可以放 1 根或 2 根木棒，放入的条件如下：

  • 若只放 1 根木棒，长度为 aa，则需满足 a≤Ca \leq C。
  • 若放 2 根木棒，长度分别为 aa 和 bb，则需满足 a+b+1≤Ca + b + 1 \leq C。

请你求出收纳所有木棒所需收纳盒的最小数量。

输入格式

输入会从标准输入按以下格式给出。

NN CC L1L_1 L2L_2 ...... LNL_N

输出格式

若最少需要 xx 个收纳盒，请输出 xx。

输入输出样例

  • 输入#1

    4 10
2
8
4
5

    输出#1

    3

  • 输入#2

    3 10
1
1
1

    输出#2

    2

  • 输入#3

    9 30
22
5
2
18
6
21
29
11
18

    输出#3

    5

说明/提示

限制条件

  • 1≤N≤1000001 \leq N \leq 100000
  • 1≤C≤1091 \leq C \leq 10^9
  • 1≤Li≤C1 \leq L_i \leq C
  • 输入均为整数

样例说明1

若将第 3 根和第 4 根木棒放在同一个收纳盒内，第 1 根和第 2 根分别单独放在收纳盒中，总共需要 3 个收纳盒。

样例说明2

请注意，每个收纳盒最多只能放 2 根木棒。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页