牛牛开了一家理发店,只有他一个理发师。
今天,来他店里的顾客特别多,于是顾客们排起了很长的队。
每个顾客因为自己的需求不一样,所以每个顾客都有自己的理发时间。
如果一个顾客他在排队时的等待时间超过了他的理发时间,他就会感到不开心,这个顾客他可能就会给牛牛的理发店打差评;反之,这位顾客会感到很开心,这个顾客他可能就会给牛牛的理发店打好评。
这下可急坏了牛牛,他想出了一个解决方法,统计一下这些顾客的需求,得到每个人的理发时间,然后对整个队伍排队的顺序进行重新分配,尽可能使更多的人对这次理发感到很开心。
只不过牛牛不知道该怎么做,他想请你帮他解决这个问题,给定n个顾客,和每个顾客的理发时间,返回重新分配后最多有多少顾客对这次理发感到很开心。
其实根据题意,我们不难想到,为了使最多的顾客对这次理发感到很开心,重新分配的策略只需要根据每个人的理发时间进行从小到大的排序即可。定义一个tmp=n,如果等待时间超出了顾客的理发时间,那么tmp--。
模拟即可,代码如下:
时间复杂度
空间复杂度
/** * 返回重新分配后最多有多少顾客对这次理发感到很开心 * @param n int整型 代表顾客的数量 * @param a int整型vector 代表每位顾客的理发时间 * @return int整型 */ int solve(int n, vector<int> &a) { // write code here int tmp = n; long long sum = 0; sort(a.begin(), a.end()); for (int i = 0; i < n; i++) { if (sum <= a[i]) { sum += a[i]; } else { tmp--; } } return tmp; }