本题需要文件读写
文件 IO 为:输入文件 part.in,输出文件 part.out。请使用上述文件名读入和输出。
题目描述
庐州吴氏船模制作技艺是蜀山区省级非遗。吴师傅有一批木制零件,共 n 个,每个零件有一个精细度 ai。
现在需要把这些零件分配到 ⌊(n+1)/2⌋ 个工序盒中。每个盒子可以装 1 个或 2 个零件(最多不超过 2 个)。同一盒内所有零件的精细度之和不能超过盒子的容量 C(如果盒子里只有 1 个零件,则该零件的精细度不能超过 C)。
希望所有盒子的统一容量 C 尽可能小。请求出满足分配条件的最小容量 C。
⌊x⌋ 表示向下取整符号,即不超过 x 的最大整数。
输入格式
第一行包含一个整数 n(2≤n≤105)—— 表示零件的数量。
第二行包含 n 个整数 a1,a2,…,an(1≤ai≤109)—— 表示每个零件的精细度。
输出格式
输出一行,一个整数,表示满足条件的最小容量 C。
样例输入 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
说明
样例解释
- 样例 1 解释:
n=4,需要 ⌊(4+1)/2⌋=2 个盒子,每个盒子恰好装 2 个零件。
配对方式:20+80=100,30+70=100,最大值为 100。
- 样例 2 解释:
n=6,需要 ⌊(6+1)/2⌋=3 个盒子,每个盒子恰好装 2 个零件。
最优配对:1+6=7,2+5=7,3+4=7,最大值为 7。
- 样例 3 解释:
n=4,需要 ⌊(4+1)/2⌋=2 个盒子。
配对方式:1+100=101,100+100=200,最大值为 200。
- 样例 4 解释:
n=5,需要 ⌊(5+1)/2⌋=3 个盒子,其中 1 个盒子装 1 个零件,2 个盒子各装 2 个零件。
最优方案:100 单独一盒,剩余 1,50,51,52 两端配对:
- 100 单独一盒;
- 1+52=53;
- 50+51=101。
最大容量 C=max(100,53,101)=101。
- 样例 5 解释:
n=3,需要 ⌊(3+1)/2⌋=2 个盒子,其中 1 个盒子装 1 个零件,1 个盒子装 2 个零件。
最优方案:8 单独一盒,3+5=8,最大容量 C=max(8,8)=8。
数据范围
对于所有测试数据,保证 2≤n≤105,1≤ai≤109。
保证所有的输入数值均为整数。
各测试点的附加限制如下表所示:
| 测试点编号 |
n≤ |
ai 范围 |
特殊性质 |
| 1∼2 |
10 |
1≤ai≤100 |
无 |
| 3∼4 |
100 |
1≤ai≤1000 |
| 5∼6 |
1000 |
1≤ai≤106 |
| 7∼8 |
105 |
1≤ai≤109 |
| 9 |
所有 ai 相同 |
| 10 |
随机数据 |