排列充电器(Arranging Adapters)

题目描述

本题对应 NWERC 2023 Problem A：Arranging Adapters。

你有一个包含 $s$ 个插孔的排插，每个插孔的宽度为 $3$ 厘米（总宽度为 $3s$ 厘米）。同时你有 $n$ 个不同宽度的充电器适配器，第 $i$ 个适配器的宽度为 $w_i$ 厘米。

排插最左端与最右端的两个插孔允许适配器向外悬空伸出，因此最左端和最右端最多可以各插 $1$ 个任意宽度的适配器且仅各占用 $1$ 个插孔（即各消耗 $3$ 厘米排插空间）。

对于其余插在中间的适配器：

• 每个宽度为 $w$ 的适配器不仅需要至少 $w$ 厘米的连续空间，而且插孔按每 $3$ 厘米一格对齐；
• 若 $w \bmod 3 = 0$，它恰好占用 $w / 3$ 个插孔；
• 若 $w \bmod 3 = 2$，它独立放置时占用 $\lceil w / 3 \rceil$ 个插孔，但若与另一个 $w' \bmod 3 = 1$ 的适配器相邻拼合，两者共占用 $(w + w') / 3$ 个插孔；
• 若两个 $w \bmod 3 = 1$ 的适配器相邻拼合，它们还可以共享中间的一个插孔间隙，共占用 $(w_1 + w_2 + 1) / 3$ 个插孔。

请你计算在这个排插上最多可以同时插上多少个适配器。

输入格式

第一行包含两个正整数 $n, s$，分别表示适配器数量与排插插孔数量。

第二行包含 $n$ 个正整数 $w_1, w_2, \dots, w_n$，表示每个适配器的宽度。

输出格式

输出一行一个整数，表示最多能同时插上的适配器数量。

样例输入 #1

4 4
5 5 5 5

样例输出 #1

3

样例输入 #2

5 5
4 4 4 7 8

样例输出 #2

4

数据范围

对于 $100\%$ 的数据，$1 \le n, s \le 2 \times 10^5$，$1 \le w_i \le 10^9$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

测试点分布

出处：原题链接