← 返回题目

题库练习选举

← 上一题下一题 →

A2667 | $选举$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

Byteland 国的居民最近一直为议会选举投票。现在，当结果公布的时候，党派不得不决定联合组建政府。 每个党派都会获得议会中的一定席位。联合政府由这些党派中的一部分组成，他们在议会中的席位数之和**严格大于**总席位数的一半。对于联合政府来说，席位越多越好。 一个**过剩**的联合政府是指联合政府中的一个党派被移出后，剩余的联合政府在国会中仍有过半数的席位。 请写一个程序能够找到一个在议会中有着**最大可能席位数**且**不过剩**的联合政府。

输入格式

标准输出的第一行包含一个整数 $n$，表示参加选举的党派数。党派被从 $1$ 到 $n$ 编号。 第二行包含 $n$ 个非负整数 $a_1,\dots ,a_n$，被一个空格隔开，$a_i$ 是第 $i$ 个党派获得的席位数。你可以假设国会中的中的总席位数为小于等于 $10^5$ 的正整数。

输出格式

包含一个整数，表示最大可能席位数。

输入输出样例

输入 #1

4
1 3 2 4

输出 #1

C++ 编辑器

输入

输出