题目描述
苏西小朋友和她的妈妈正在超市里购物,看着收银处排着的长长的队伍,她就想如何能够提高整体的服务质量呢?
已知,现在有n个人正在排队等待结账,每个人结账所花的时间都可能是不同的,第 i 个人的结账时间为ti。
如果一个人在队伍中的等待时间超过了他自己结账所花的时间,那么他就会很不满意。
一个人在队伍中的等待时间等于他前面所有人结账所花的时间的总和。
苏西认为,如果我们合理安排队伍中人群的结账次序,就可以使得更多的人能够感到满意。
请问,能够感到满意的人数最多是多少。
输入格式
第一行包含整数n。
第二行包含n个整数ti,表示队列中的每个人结账所需的时间。
输出格式
一个整数,表示能够感到满意的最大人数。
数据范围
1≤n≤105
1≤ti≤109
样例
输入样例:
5
15 2 1 5 3
输出样例:
4
算法1
看样例 就是排序,然后按照题意找出 前面数之和不大于自己的数字
注意和是LONG LONG 就交了一发试试 AC
C++ 代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int main()
{
int n;
cin >> n;
for(int i =0;i <n;i++){
int t;
cin >> t;
v.push_back(t);
}
sort(v.begin(),v.end());
long long sum = 0; int count = 0;
for (int i = 0; i < v.size(); i++)
{
if (v[i] >= sum) {
count++;
sum += v[i];
}
}
cout << count << endl;
return 0;
}
排好序,判断条件哪里写错了,看了你的之后,一下子就理解了,多谢多谢!!!