6978: 排队购物

内存限制:10 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:10 通过:5

题目描述

苏西小朋友和她的妈妈正在超市里购物,看着收银处排着的长长的队伍,她就想如何能够提高整体的服务质量呢?

已知,现在有 n 个人正在排队等待结账,每个人结账所花的时间都可能是不同的,第 i 个人的结账时间为 ti。

如果一个人在队伍中的等待时间超过了他自己结账所花的时间,那么他就会很不满意。

一个人在队伍中的等待时间等于他前面所有人结账所花的时间的总和。

苏西认为,如果我们合理安排队伍中人群的结账次序,就可以使得更多的人能够感到满意。

请问,能够感到满意的人数最多是多少。 

输入格式

第一行包含整数 n。 

第二行包含 n 个整数 ti,表示队列中的每个人结账所需的时间。

输出格式

 一个整数,表示能够感到满意的最大人数。 

数据范围

1≤n≤105
1≤ti≤109

输入样例:

5
15 2 1 5 3

输出样例:

4

样例解释

一种可行的排队方式为 1 2 3 5 15,这样除了排在第四位的人会感到不满意以外,其他的人都会满意。 

所以答案是 4。 

输入样例 复制

5
15 2 1 5 3

输出样例 复制

4

分类标签