AT_joi2026_yo2_b.究極の団子職人 (Ultimate Dango Maker)

普及/提高-

通过率：0%

AC君温馨提醒

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

题目描述

JOI 君是一名团子工匠。有 $N$ 种颜色的团子，颜色编号从 $1$ 到 $N$ ，JOI 君拥有颜色 $i$ （ $1 \leq i \leq N$ ）的团子 $A_i$ 个。

JOI 君可以从他拥有的团子中选择 $3$ 个，制作一串串团子。但选择的 $3$ 个团子的颜色 $c_1, c_2, c_3$ （ $1 \leq c_1 \leq N$ ， $1 \leq c_2 \leq N$ ， $1 \leq c_3 \leq N$ ）需要满足： $c_1$ 与 $c_2$ 的差、 $c_2$ 与 $c_3$ 的差、 $c_3$ 与 $c_1$ 的差都不超过 $1$ ，即以下条件全部满足：

$|c_1 - c_2| \leq 1$
$|c_2 - c_3| \leq 1$
$|c_3 - c_1| \leq 1$

同一个团子不能在多串串团子中重复使用。JOI 君希望通过巧妙选择团子，使制作的串团子数目尽可能多。

请你根据所给团子的信息，计算 JOI 君最多可以制作多少串串团子。

输入格式

输入如下格式：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出 JOI 君最多能制作的串团子数，输出一行。

输入输出样例

输入#1
```
3
3 1 2
```
输出#1
```
2
```
输入#2
```
1
99
```
输出#2
```
33
```
输入#3
```
2
5 6
```
输出#3
```
3
```
输入#4
```
6
0 2 2 3 1 2
```
输出#4
```
3
```
输入#5
```
1
0
```
输出#5
```
0
```

说明/提示

小子任务

( $6$ 分) $N=1$ 。
( $9$ 分) $N \leq 2$ 。
( $10$ 分) 所有 $A_i$ 都是 $3$ 的倍数（ $1 \leq i \leq N$ ）。
( $17$ 分) $A_i = 2$ （ $1 \leq i \leq N$ ）。
( $21$ 分) $A_i \leq 3$ （ $1 \leq i \leq N$ ）。
( $37$ 分) 无额外限制。

样例解释 1

可以用颜色 $1$ 的团子 $3$ 个做 $1$ 串，用颜色 $2$ 的团子 $1$ 个和颜色 $3$ 的团子 $2$ 个做 $1$ 串，共制作 $2$ 串串团子。第一串 $|1-1|=0\leq1$ ，第二串 $|2-3|\leq 1$ ， $|3-3|\leq 1$ ，所以团子的选择满足条件。不能制作超过 $2$ 串，因此输出 $2$ 。

该样例满足小子任务 $5, 6$ 的约束。

样例解释 2

可以用颜色 $1$ 的团子每 $3$ 个做 $1$ 串，总共 $33$ 串。不能制作更多串串团子，因此输出 $33$ 。

该样例满足小子任务 $1, 2, 3, 6$ 的约束。

样例解释 3

可以用颜色 $1$ 的团子 $3$ 个做 $1$ 串，用颜色 $1$ 的团子 $2$ 个和颜色 $2$ 的团子 $1$ 个做 $1$ 串，用颜色 $2$ 的团子 $3$ 个做 $1$ 串，共制作 $3$ 串串团子。不能制作超过 $3$ 串，因此输出 $3$ 。

该样例满足小子任务 $2, 6$ 的约束。

样例解释 4

该样例满足小子任务 $5, 6$ 的约束。

样例解释 5

该样例满足小子任务 $1, 2, 3, 5, 6$ 的约束。

数据范围

$1 \leq N \leq 200\,000$ 。
$0 \leq A_i \leq 10^9$ （ $1 \leq i \leq N$ ）。
所有输入值均为整数。

由 ChatGPT 5 翻译

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

首页