#P18902. [2026多校联测]小Z爱优化
[2026多校联测]小Z爱优化
题目背景
奋战三星期,造台计算机……
小 Z 手搓的计算机近期成功运行,但是他发现计算机在运行不同任务时所花费的时间相差巨大,因此他希望对计算机的任务处理系统进行一些优化。
题目描述
小 Z 规划了 个依次执行的任务,其中执行第 个任务所花费的时间为 。
改进后的计算机可以将这 个任务分为若干组,每组包含恰好一个任务,或恰好两个相邻的任务。每一组执行的时间为组中各任务执行时间之和。
小 Z 不希望某两组任务的执行时间相差太大,因此他想知道,在所有分组方式中,各组执行时间的极差的最小值是多少。
输入格式
本题包含多组数据。
第一行包含一个正整数 ,表示数据组数。
接下来 组数据,每组第一行包含一个正整数 ,表示任务个数。
第二行包含 个正整数,表示各任务的执行时间。
输出格式
对每组数据,输出一行一个整数,表示答案。
样例 1
2
6
1 1 4 5 1 4
6
1 9 1 9 8 10
3
2
数据范围
对所有数据,保证 ,,,。
| 测试点编号 | |||
|---|---|---|---|
| 1-4 | |||
| 5-9 | |||
| 10-13 | |||
| 14-16 | |||
| 17-20 |