题意:n个人在超市排队买单。每个人花费的时间为a[i]。如果第i个人排队的时间大于买单的时间,那个人就会发火。问,最少可以让几个人不发火。

数据分析:1 ≤ n ≤ 105 :: 1 ≤ a[i] ≤ 1e9

思路:
1·错误思路:必须要让时间小的先买单,那么sort一下。然后求前缀和,再O(n)for一遍。如果sum[i] > a[i] ans++。

2.正确思路:假如第i个人生气了,那么这个人去后面排队。如果还让他买单,只会让后面生气的人数可能性增加。

复杂度分析:(nlogn+n)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=1e5+50;
int a[maxn];
ll sum[maxn];
ll ans=0;

int main(void)
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n); // 时间
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]<sum)
        {
            ans++;
            continue;
        }
        else    sum+=a[i];
    }
    cout << n-ans <<endl;
}