徐老师的最强大脑
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师最近打算办一场最强大脑比拼！他决定用最传统的答题模式来比拼，每次徐老师会提出一个问题，比拼双方如果有人回答不出问题则判失败
现在徐老师邀请了 $n$ 位同学来参加比拼，为了方便理解，徐老师将每位同学的实力进行了数字化
对于第 $i$ 位同学来说，徐老师认为他的实力可以转化成答题量 $a_i$，也就是说这位同学的实力支持他最多回答出 $a_i$ 道题
当比拼双方有人的答题量变为 $0$ 的时候则判定失败，获胜者会留在台上和下一位同学继续比拼，如果双方同时失败则认为获胜者的剩余答题量为 $0$，接下来上台的同学不需要和他比拼直接获得胜利
现在徐老师可以随意安排所有人的上台比拼顺序，为了让这次比拼有看头，他想知道怎么安排比拼顺序可以使得最后留在台上的获胜者的剩余答题量尽可能小？
比如有 $7$ 位同学，答题量分别为 $5,4,9,3,4,6$
徐老师可以安排比拼顺序为 $9,5,4,6,3,4,0$
第一次比拼为 $(9,5)$，获胜者剩余答题量为 $4$，和下一位同学继续比拼
第二次比拼为 $(4,4)$，双方同时失败，获胜者剩余答题量为 $0$，下一位同学 $6$ 上台直接获胜
第三次比拼为 $(6,3)$，获胜者剩余答题量为 $3$，和下一位同学继续比拼
第三次比拼为 $(3,4)$，获胜者剩余答题量为 $1$
第四次比拼为 $(1,0)$，因为最后一位同学的答题量为 $0$，所以不需要比拼，上台即失败，获胜者剩余答题量为 $1$
输入格式
第一行一个整数 $n$ 表示同学人数接下来一行包含 $n$ 个整数，分别表示每位同学的答题量
| 测试点编号 | 特殊性质 |
| :---: | :---: |
| $1 \sim 2$ | $a_i=0/1$ |
| $3 \sim 5$ | $a_i=i$ |
| $6 \sim 8$ | $n \leq 15$ |
| $9 \sim 10$ |无|
对于所有的数据，有 $1 \leq n \leq 100, a_i \geq 0, \sum{a_i} \leq 10^6$
输出格式
输出最后获胜者最小的剩余答题量样例
7
9 5 4 3 4 6 0123CSP-J秋季普及组模拟赛(6)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 4
- 开始于
- 2023-10-2 12:30
- 结束于
- 2023-10-12 12:30
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 52
