C. 零件(part)

    传统题 文件IO:part 1000ms 256MiB

零件(part)

本题需要文件读写

文件 IO 为:输入文件 part.in,输出文件 part.out。请使用上述文件名读入和输出。

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

庐州吴氏船模制作技艺是蜀山区省级非遗。吴师傅有一批木制零件,共 nn 个,每个零件有一个精细度 aia_i。

现在需要把这些零件分配到 ⌊(n+1)/2⌋\lfloor(n+1)/2\rfloor 个工序盒中。每个盒子可以装 11 个或 22 个零件(最多不超过 22 个)。同一盒内所有零件的精细度之和不能超过盒子的容量 CC(如果盒子里只有 11 个零件,则该零件的精细度不能超过 CC)。

希望所有盒子的统一容量 CC 尽可能小。请求出满足分配条件的最小容量 CC。

⌊x⌋\lfloor x \rfloor 表示向下取整符号,即不超过 xx 的最大整数。

输入格式

第一行包含一个整数 nn(2≤n≤1052 \le n \le 10^5)—— 表示零件的数量。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n(1≤ai≤1091 \le a_i \le 10^9)—— 表示每个零件的精细度。

输出格式

输出一行,一个整数,表示满足条件的最小容量 CC。

样例输入 1

4
30 70 20 80

样例输出 1

100

样例输入 2

6
1 2 3 4 5 6

样例输出 2

7

样例输入 3

4
1 100 100 100

样例输出 3

200

样例输入 4

5
1 50 51 52 100

样例输出 4

101

样例输入 5

3
5 8 3

样例输出 5

8

说明

样例解释

  • 样例 11 解释: n=4n=4,需要 ⌊(4+1)/2⌋=2\lfloor(4+1)/2\rfloor=2 个盒子,每个盒子恰好装 22 个零件。 配对方式:20+80=10020+80=100,30+70=10030+70=100,最大值为 100100。
  • 样例 22 解释: n=6n=6,需要 ⌊(6+1)/2⌋=3\lfloor(6+1)/2\rfloor=3 个盒子,每个盒子恰好装 22 个零件。 最优配对:1+6=71+6=7,2+5=72+5=7,3+4=73+4=7,最大值为 77。
  • 样例 33 解释: n=4n=4,需要 ⌊(4+1)/2⌋=2\lfloor(4+1)/2\rfloor=2 个盒子。 配对方式:1+100=1011+100=101,100+100=200100+100=200,最大值为 200200。
  • 样例 44 解释: n=5n=5,需要 ⌊(5+1)/2⌋=3\lfloor(5+1)/2\rfloor=3 个盒子,其中 11 个盒子装 11 个零件,22 个盒子各装 22 个零件。 最优方案:100100 单独一盒,剩余 1,50,51,521, 50, 51, 52 两端配对:
    • 100100 单独一盒;
    • 1+52=531+52=53;
    • 50+51=10150+51=101。 最大容量 C=max⁡(100,53,101)=101C = \max(100, 53, 101) = 101。
  • 样例 55 解释: n=3n=3,需要 ⌊(3+1)/2⌋=2\lfloor(3+1)/2\rfloor=2 个盒子,其中 11 个盒子装 11 个零件,11 个盒子装 22 个零件。 最优方案:88 单独一盒,3+5=83+5=8,最大容量 C=max⁡(8,8)=8C = \max(8, 8) = 8。

数据范围

对于所有测试数据,保证 2≤n≤1052 \le n \le 10^5,1≤ai≤1091 \le a_i \le 10^9。 保证所有的输入数值均为整数。

各测试点的附加限制如下表所示:

测试点编号 n≤n \le aia_i 范围 特殊性质
1∼21 \sim 2 1010 1≤ai≤1001 \le a_i \le 100 无
3∼43 \sim 4 100100 1≤ai≤10001 \le a_i \le 1000
5∼65 \sim 6 10001000 1≤ai≤1061 \le a_i \le 10^6
7∼87 \sim 8 10510^5 1≤ai≤1091 \le a_i \le 10^9
99 所有 aia_i 相同
1010 随机数据
无金币奖励

2026合肥市蜀山区区赛小学组自测【民间数据】

未参加
状态
已结束
规则
IOI
题目
4
开始于
2026-10-19 22:15
结束于
2026-11-9 18:15
持续时间
500 小时
主持人
参赛人数
30