题意: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;
}